Интересно, если С# и Java-грамматики LALR (x)? Если да, то какое значение x?
Edit:
После принятия истинного ответа, я думаю, что лучше изменить Q таким образом:
Есть ли какой-нибудь парсер LALR (x), который мог бы анализировать текущие версии Java (версия 7) или С# (версия 4)? Если да, то каково значение x?
Вы не можете задать этот вопрос без предварительного указания конкретной грамматики для langauge, поскольку некоторые грамматики могут быть, а некоторые не могут.
Возможно, вы имеете в виду грамматику Java, опубликованную в последних спецификациях Java. Вы имеете в виду для Java 7?
Я не уверен, что вы можете назначить определенную грамматику для С#, по крайней мере, не от Microsoft, особенно для С# 4.0; Я не верю, что они опубликовали грамматику.
Я могу сказать, что я не думаю, что С# может быть LALR (x), потому что у него есть некоторые элементы, которые выглядят как идентификаторы, но могут быть ключевыми словами в определенных контекстах. Это требует, чтобы лексер знал, что синтаксический анализатор должен решить, является ли токен, подобный идентификатору, ключевым словом, или просто и идентификатором. Таким образом, должна быть обратная связь от синтаксического анализатора до lexer, или лексер должен производить оба токена и передавать их парсеру, чтобы решить, что он хочет. Анализаторы LALR определяются на токенах без обратной связи и где каждый входной токен имеет только одну интерпретацию.
Я не думаю, что Java тоже, от Java 1.5 и выше, когда enum был введен как особый тип со своим ключевым словом. Это связано с тем, что для компиляторов Java 1.5 для обработки существующих программ Java 1.4, которые использовали enum в качестве имени переменной, перечисление должно рассматриваться как ключевое слово в некоторых контекстах и как имя переменной в других. Таким образом, анализатор Java 1.5 имеет те же проблемы, что и С#.
Как практический вопрос, никакие реальные langauges не являются LALR (1) [первая версия Java может быть исключением], и любой, кто создает реальный парсер (esp LALR), должен сделать какой-то взломать, чтобы обойти это. (GCC лихо проанализировал С++ с помощью анализатора LALR с ужасным взломом таблицы символов в течение долгого времени, поэтому он мог определить разницу между идентификатором как переменной и идентификатором в качестве экземпляра typedef. Теперь он имеет какую-то ручную реализацию рекурсивный парсер спуска, но я думаю, что ужасный взлом остается). Поэтому я не уверен, насколько важно ответить на ваш вопрос.
Наши члены С# 4.0 и Java 7 нашего семейства языков переднего плана анализируют языки, используя парсер GLR, расширенный как с обратной связью способность и способность обрабатывать две интерпретации одного и того же токена. GLR ставит вопрос о LALR (x) спорным, а обратная связь и множественные интерпретации позволяют нам обрабатывать многие языки, которые также будут за пределами чистой возможности GLR.
EDIT: после некоторого раздумья, может быть, действительно уродливый способ заставить оба грамматики обрабатывать свое ключевое слово в контексте. В качестве примера можно использовать Java enum. Там реалистично должно быть правило грамматики:
type = 'enum' '{' enum_members '}' ;
Но нам также нужно разрешить "перечисление" как идентификатор. Мы можем это сделать, заменив терминальный токен идентификатор с нетерминалом:
identifier = IDENTIFIER | 'enum' ;
и настаивайте на том, что IDENTIFIER - это терминалы, созданные лексером. Теперь, по крайней мере, лексер не должен решать, как обращаться с перечислением; парсер делает. Но ваша обозначенная грамматика должна была бы сформироваться так, чтобы иметь шанс получить LALR (x).
Наши парсеры использовали это, чтобы иногда использовать некоторые ключевые слова в качестве идентификаторов. Мы изменили наш синтаксический движок, как описано выше, и больше не делаем этого.
Явная грамматика Java (версия 1.0) известна как LALR (1); этот сайт предоставляет грамматику и начинается с уведомления, что
Грамматика была механически проверена, чтобы гарантировать, что это LALR (1).
Я не уверен, является ли С# LALR (1), но существует С# parser, написанный в 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