Что упрощает синтаксический анализ Java, чем C?

90

Я знаком с тем фактом, что грамматики C и C ++ контекстно-зависимы , и, в частности, вам понадобится «взлом лексера» в C. С другой стороны, у меня сложилось впечатление, что вы можете анализировать Java только с 2 токена предвидения, несмотря на значительное сходство между двумя языками.

Что бы вам нужно было изменить в C, чтобы сделать его более удобным для анализа?

Я спрашиваю, потому что все примеры контекстной чувствительности C, которые я видел, технически допустимы, но ужасно странны. Например,

foo (a);

может вызывать функцию void fooс аргументом a. Или он может быть объявлен aкак объект типа foo, но вы можете так же легко избавиться от скобок. Частично эта странность возникает из-за того, что производственное правило «прямого декларатора» для грамматики C выполняет двойную цель объявления как функций, так и переменных.

С другой стороны, грамматика Java имеет отдельные производственные правила для объявления переменных и объявления функций. Если вы напишете

foo a;

тогда вы знаете, что это объявление переменной и fooоднозначно может быть проанализировано как имя типа. Это может быть недопустимый код, если класс fooне был определен где-то в текущей области, но это задание для семантического анализа, которое может быть выполнено на более позднем этапе компилятора.

Я видел, как было сказано, что C трудно разбирать из-за typedef, но вы также можете объявлять свои собственные типы в Java. Какие правила грамматики C, кроме того direct_declarator, ошибочны?

Коррок
источник
7
Классный вопрос. Возможно, слишком широко или в первую очередь самоуверенно.
asteri
37
Это верный вопрос о синтаксических анализаторах, и единственное, что широко или основано на нем, - это последние пару предложений (которые, вероятно, следует отбросить или изменить). Выйти с близкими голосами.
R .. GitHub НЕ ПОМОГАЕТ ICE
1
Я соответствующим образом отредактировал вопрос, спасибо @R .. за отзыв.
korrok
3
Практически каждый (стандартный) компьютерный язык зависит от контекста ; вы не можете объявить переменную одного типа и неправильно использовать ее в большинстве языков . Это отличается от того, что «все грамматики языка» контекстно-зависимы; большинство людей, создающих парсеры, строят контекстно-свободный (или даже более ограничительный) парсер, а затем используют хаки вне парсера для проверки контекстно-свободных свойств.
Ира Бакстер
1
@IraBaxter Я бы не назвал это "взломами". Разделение проблемы на две кажется разумным, поскольку синтаксический анализ контекстно-зависимых языков не может быть выполнен эффективно (и на самом деле даже анализ контекстно-свободных языков неэффективен, и поэтому мы обычно ограничиваемся подмножествами контекстно-свободных языков) . Контекстно-свободный синтаксический анализ + статический анализ для проверки только контекстно-зависимых свойств через AST - это разумная вещь.
Bakuriu

Ответы:

76

Разбирать C ++ становится все труднее. Парсинг Java становится таким же трудным.

См. Этот SO-ответ, в котором обсуждается, почему C (и C ++) «трудно» анализировать . Вкратце, грамматики C и C ++ по своей сути неоднозначны; они дадут вам несколько синтаксических анализов, и вы должны использовать контекст для разрешения неоднозначности. Затем люди совершают ошибку, предполагая, что вы должны разрешать неоднозначности в процессе синтаксического анализа; не так, см. ниже. Если вы настаиваете на разрешении двусмысленностей во время синтаксического анализа, ваш синтаксический анализатор становится более сложным и его труднее строить; но эта сложность - рана, нанесенная самому себе.

IIRC, «очевидная» грамматика LALR (1) Java 1.4 не была двусмысленной, поэтому ее было «легко» разобрать. Я не уверен, что современная Java не имеет, по крайней мере, локальных двусмысленностей на большом расстоянии; всегда есть проблема решить, закрывает ли "... >>" два шаблона или является "оператором сдвига вправо". Я подозреваю, что современная Java больше не анализирует с помощью LALR (1) .

Но можно обойти проблему синтаксического анализа, используя сильные синтаксические анализаторы (или слабые синтаксические анализаторы и взломы коллекции контекста, как сейчас в основном делают интерфейсы C и C ++) для обоих языков. C и C ++ имеют дополнительную сложность, связанную с наличием препроцессора; на практике это сложнее, чем кажется. Одно из заявлений состоит в том, что синтаксические анализаторы C и C ++ настолько сложны, что их приходится писать вручную. Это неправда; вы можете создавать парсеры Java и C ++ с помощью генераторов парсеров GLR.

Но проблема не в парсинге.

После синтаксического анализа вы захотите что-нибудь сделать с деревом AST / синтаксического анализа. На практике вам необходимо знать для каждого идентификатора, каково его определение и где он используется («разрешение имени и типа», небрежно, построение таблиц символов). Оказывается, это НАМНОГО больше работы, чем создание правильного парсера, усугубляемое наследованием, интерфейсами, перегрузкой и шаблонами, и сбивается с толку тем фактом, что семантика для всего этого написана на неформальном естественном языке, разбросанном на десятки или сотни страниц. стандарта языка. C ++ здесь действительно плохой. Java 7 и 8 становятся довольно ужасными с этой точки зрения. (И таблицы символов - это не все, что вам нужно; см. Мое более длинное эссе «Жизнь после анализа»).

Большинство людей борются с чистой частью синтаксического анализа (часто никогда не заканчивают; проверьте саму SO на множество, много вопросов о том, как создавать рабочие синтаксические анализаторы для реальных языков), поэтому они никогда не видят жизни после синтаксического анализа. А потом мы получаем народные теоремы о том, что трудно разобрать, и нет никаких сигналов о том, что происходит после этого этапа.

Исправление синтаксиса C ++ никуда не приведет.

Что касается изменения синтаксиса C ++: вы обнаружите, что вам нужно исправить множество мест, чтобы позаботиться о множестве локальных и реальных неоднозначностей в любой грамматике C ++. Если вы настаиваете, следующий список может стать хорошей отправной точкой . Я считаю, что нет смысла делать это, если вы не являетесь членом комитета по стандартам C ++; если бы вы сделали это и построили компилятор, использующий это, никто в здравом уме не стал бы его использовать. В существующие приложения C ++ вложено слишком много средств, чтобы их можно было переключить для удобства разработчиков, создающих парсеры; к тому же их боль прошла, и существующие парсеры работают нормально.

Вы можете написать свой собственный парсер. Хорошо, это нормально; просто не ждите, что остальная часть сообщества позволит вам изменить язык, который они должны использовать, чтобы вам было легче. Все они хотят, чтобы для них было проще - использовать язык в том виде, в каком он задокументирован и реализован.

Ира Бакстер
источник
Хороший ответ. См. Также D и C +, которые пытаются решить некоторые из этих проблем. s / content /
Contend
3
Я читал «Жизнь после разбора» раньше и обнаружил, что это открыло мне глаза; он дал мне понять, что семантический анализ (разрешение имени / типа, ...) требует гораздо больше работы, чем синтаксический анализ. Я не пытаюсь изменить синтаксис какого-либо языка. Я действительно хочу понять, каковы свойства языка, на котором вы можете сначала провести синтаксический анализ, а затем семантический анализ. C не является таким языком (требуется взлом лексера); Я всегда думал, что это Java, и хочу знать, почему.
korrok
1
@Korrok: прочтите мой ответ о создании Java / C ++ с использованием парсеров GLR. Вам не нужен взлом лексера . Итак, различие в уме людей, которые используют неправильную технологию синтаксического анализа. ... Конечно, создание полного интерфейса C ++ (особенно C ++ 14, который мы сделали) сложнее, чем создание Java8, но они оба сложны (с точки зрения усилий и внимания к деталям) и анализируют это самая легкая штука.
Ира Бакстер
1
Я согласен с вашей «жизнью после разбора»: например, разрешение перегрузки в C # может кодировать любую проблему 3-SAT и, таким образом, является NP-трудным.
Jörg W Mittag