Являются ли грамматики C# и Java LALR(x)?
Интересно, грамматики C# и Java LALR(x)? Если да, каково значение х?
Редактировать:
Приняв верный ответ, я думаю, что лучше изменить Q следующим образом:
Есть ли анализатор LALR (x), который мог бы анализировать текущие выпуски Java (версия 7) или C# (версия 4)? Если да, каково значение х?
3 ответа
Вы не можете задать этот вопрос, предварительно не назначив определенную грамматику для языка, как могут быть некоторые грамматики, а некоторые нет.
Возможно, вы имеете в виду грамматику Java, опубликованную в последних спецификациях Java. Вы имеете в виду Java 7?
Я не уверен, что вы можете назначить конкретную грамматику для C#, по крайней мере, для Microsoft, особенно для C# 4.0; Я не верю, что они опубликовали грамматику.
Я могу сказать вам, что я не думаю, что C# может быть LALR(x), потому что он имеет некоторые элементы, которые выглядят как идентификаторы, но могут быть ключевыми словами в определенных контекстах. Это требует, чтобы лексер знал, что ожидает анализатор, чтобы решить, является ли идентифицирующий маркер токен ключевым словом или просто и идентификатором. Таким образом, должна быть обратная связь от парсера к лексеру, или лексер должен произвести оба токена и передать их парсеру, чтобы решить, какой он хочет. Парсеры LALR определяются в потоках токенов без обратной связи, и каждый входной токен имеет только одну интерпретацию.
Я не думаю, что Java, начиная с версии 1.5 и выше, когда enum был представлен как специальный тип со своим собственным ключевым словом. Это связано с тем, что для того, чтобы компиляторы Java 1.5 обрабатывали существующие программы Java 1.4, которые использовали enum в качестве имени переменной, enum должен рассматриваться как ключевое слово в некоторых контекстах и как имя переменной в других. Так что синтаксический анализатор Java 1.5 имеет те же проблемы, что и C#.
С практической точки зрения, настоящие языки не являются LALR(1) [первое издание Java может быть исключением], и любой, кто создает реальный синтаксический анализатор (особенно LALR), должен сделать что-то вроде хака, чтобы обойти это. (GCC лихо анализировал C++ с помощью анализатора LALR с ужасным взломом таблицы символов в течение длительного времени, поэтому он мог определить разницу между идентификатором как переменной и идентификатором как экземпляром typedef. Теперь он имеет своего рода реализованный вручную парсер рекурсивного спуска, но я думаю, что ужасный взлом остается). Поэтому я не уверен, стоит ли отвечать на ваш вопрос.
Наши члены семейства языков C# 4.0 и Java 7 анализируют языки, используя синтаксический анализатор GLR, расширенный как возможностью обратной связи, так и возможностью обрабатывать две интерпретации одного и того же токена. РВО делает вопрос LALR (х) тоо, а обратная связь и множественные интерпретации позволяют нам обрабатывать множество языков, которые были бы вне возможности чистых РВ, тоже.
РЕДАКТИРОВАТЬ: После недолгого размышления может быть действительно уродливый способ заставить обе грамматики обрабатывать свои ключевые слова в контексте. Давайте использовать перечисление Java в качестве примера. Там реально должно быть грамматическое правило:
type = 'enum' '{' enum_members '}' ;
Но нам также нужно разрешить enum в качестве идентификатора. Мы можем сделать это, заменивидентификатор токена терминала на нетерминал:
identifier = IDENTIFIER | 'enum' ;
и настаивать на том, что ИДЕНТИФИКАТОРЫ являются терминалами, произведенными лексером. Теперь, по крайней мере, лексеру не нужно решать, как лечить enum; парсер делает. Но ваша назначенная грамматика должна иметь такую форму, чтобы даже иметь шанс стать LALR (x).
Наши парсеры делали это, чтобы позволить некоторым ключевым словам иногда использоваться в качестве идентификаторов. Мы изменили наш механизм синтаксического анализа, как описано ранее, и больше не делаем этого.
Известно, что грамматика Java (версия 1.0) - LALR(1); этот сайт предоставляет грамматику и начинается с уведомления о том, что
Грамматика была механически проверена, чтобы убедиться, что это LALR(1).
Я не уверен, является ли C# LALR(1), но есть синтаксический анализатор C#, написанный наbison доступно здесь, что говорит о том, что это, вероятно, LALR (1) (при условии, что вы разрешаете объявления приоритетов).
Что бы это ни стоило, обычно LALR (1) - единственный используемый анализатор LALR. Если вам нужно использовать что-то вроде LALR (2) для грамматики, обычно лучше использовать синтаксический анализатор LALR (1) с явным устранением неоднозначности приоритета или более мощный анализатор, такой как анализатор GLR.
Надеюсь это поможет!
По крайней мере, для Java (версия 1.0) это: http://java.sun.com/docs/books/jls/first_edition/html/19.doc.html