Является ли грамматика выражения LBA (1)?

Вопрос, который я хочу задать, явно указан в названии. Позвольте мне привести пример рассматриваемой грамматики:

identifier_list
 : identifier
 | identifier_list identifier;
lambda_arguments
 : '(' identifier_list ')'
 | identifier;
lambda
 : lambda_arguments '=>' expression

Затем мы добавляем грамматику выражения нормали C, в частности,

primary_expression
 : '(' expression ')'
 | identifier
 | lambda;

Реальный вопрос заключается в том, является ли эта грамматика LALR (1) понятной, то есть способной анализироваться автоматическими генераторами парсера? Или это требует ручного или GLR-анализатора? Обратите внимание, что я хочу знать конкретно об этом подразделе, а не в контекстно-зависимом ключевом слове или в любом другом разделе.

То, что я сейчас думаю, состоит в том, что если парсер видит '(' identifier ')', у него есть два действительных разбора, поэтому, если синтаксический анализатор видит identifier, смотрит вперед на ')', он не сможет решить которые обрабатывают дерево, чтобы спуститься вниз. Это может быть просто конфликт смены/сокращения, хотя я мог бы устранить, назначив некоторый произвольный приоритет (вероятно, способствующий '(' identifier ')').

Изменить: На самом деле, я рассматривал кражу, используя этот подраздел грамматики для аналогичной функции на новом языке. У меня уже есть анонимные функции, похожие на JavaScript в грамматической форме, но мои отзывы жалуются, что они слишком многословны для многих применений, и указали выражения лямбда С# как более идеальное решение. Я был обеспокоен потенциальной двусмысленностью, вызванной этим решением. Итак, действительно, меня интересовал только этот подраздел. Другие вещи, такие как generics и casts, не являются вопросами для меня.

Предыдущие выпуски моей грамматики механически разборчивы, и я не хочу потерять это свойство, и мой предыдущий опыт работы с механическим генератором говорит мне, что лучше всего проверить здесь, а не попробовать себя. Для моего ручного парсера я мог бы, конечно, просто специальный случай '(' identifier смотреть вперед немного дальше, чем обычно.

4 ответа

Грамматика выражения, дополненная С# -style lambdas, не LALR (1), но она, вероятно, LALR (2). Следовательно, возможно (хотя и не обязательно тривиально) производить эквивалентную грамматику LALR (1): см. Ниже.

На вход вы получите конфликт уменьшения/уменьшения:

( id )

потому что id может быть сведен к identifier_list или к expression (косвенно, во втором случае), и синтаксический анализатор не может определить, какой из них правильный, на основе одного токена ()).

Он может быть основан на двух жетонах, поскольку сокращение identifier_list возможно только в том случае, если второй следующий токен равен =>, и пока => не является оператором на вашем языке, expression сокращение невозможно, если второй следующий токен равен =>. Поэтому я думаю, что это, вероятно, LALR (2), хотя я не могу сказать это с уверенностью.

Случай, когда имеется более одного идентификатора, не является проблематичным, поскольку в

( id1 id2 )

id1 id2 нельзя свести к выражению (в большинстве языков выражений, ваше, конечно, может отличаться). Случай, когда сразу один unparenthesized identifier следует за =>, также не является проблематичным при условии, что `= > 'не является допустимым оператором.

Edit

Я забыл упомянуть в своем первоначальном ответе, что нет такой вещи, как язык LALR (2). Язык, признанный грамматикой LALR (2), также распознается некоторой грамматикой LALR (1). Фактически, есть конструктивное доказательство этого утверждения, которое позволяет механическое создание такой грамматики LALR (1), а также процедуру восстановления исходного дерева синтаксического анализа.

В этом случае еще проще генерировать грамматику LALR (1), поскольку, как упоминалось выше, существует только одно производство, которое требует дополнительного поиска. Решение состоит в том, чтобы отложить сокращение на один токен. Другими словами, в исходной грамматике есть что-то вроде:

primary: '(' expression ')'
lambda_parameters: '(' id_list ')'

где оба id_list и expression выводят терминал id. Помимо id, выводы этих двух нетерминалов не пересекаются, поэтому мы могли бы решить проблему следующим образом:

primary: '(' expression_not_id ')'
 | '(' ID ')'
lambda_parameters: '(' id_list_not_id ')'
 | '(' ID ')' "

Осталось только разделить произведения на expression и id_list, чтобы отделить случай id, что оказывается не очень сложным. Ниже приведен упрощенный пример, который можно легко расширить; он ограничивается добавлением, умножением и функцией приложения (которое я включил, чтобы продемонстрировать, что два разделенных запятыми списков не являются проблемой):

%token ID LITERAL RIGHT_ARROW
%start expr
%%
primary: primary_not_id | ID ;
term: term_not_id | ID ;
sum: sum_not_id | ID ;
expr: expr_not_id | ID ;
expr_list: expr | expr_list ',' expr ;
arguments: '(' ')' | '(' expr_list ')' ;
ids: ID ',' ID | ids ',' ID ;
parameters: '(' ID ')' | '(' ids ')' ;
primary_not_id: LITERAL
 | '(' expr_not_id ')'
 | '(' ID ')'
 | primary arguments
 ;
term_not_id: primary_not_id
 | term '*' primary
 ;
sum_not_id: term_not_id
 | sum '+' term
 ;
expr_not_id: sum_not_id
 | parameters RIGHT_ARROW expr
 ;

Примечание. Грамматика в OP создает lambdas с несколькими параметрами в виде последовательности идентификаторов, не разделенных запятыми: (a b) => a + b. Я думаю, что фактическое намерение состояло в том, чтобы использовать запятые: (a, b) => a + b, и то, что я сделал в вышеупомянутой грамматике. Разница важна, если ваш язык имеет оператор запятой, как это делает семейство C, потому что в этом случае выражение может быть '(' expression_list ')', что противоречит списку параметров лямбда. Наивная реализация привела бы к конфликту уменьшения/уменьшения в первом expression в expression_list, который не может быть разрешен с помощью конечного вида, так как expression_list может быть сколь угодно длинным.

Существует также решение для этого случая: оно состоит из выделения id_list из expression_list, примерно следующего:

id_list: ID
 | id_list ',' ID
 ;
expression_list_not_id_list: expression_not_id
 | id_list ',' expression_not_id
 | expression_list_not_id_list ',' expression
 ;
expression_list: expression_list_not_id_list
 | id_list
 ;

Я не занимался полной грамматикой, так как не знаю, чего требует целевой язык.


Во-первых, теория парсера всегда была одной из моих слабых сторон. В основном я работаю над семантическими анализаторами.

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

Итак, я говорю здесь, чтобы взять этот ответ с достаточным количеством скептицизма.

Как вы заметили, lambdas слегка раздражает, потому что вы должны быть осторожны в этом выражении в скобках - это может быть выражение в скобках, оператор литья или список параметров лямбда, а список параметров лямбда может быть в нескольких различных форм. Но все рассмотренные вещи, добавив лямбда на С# 3.0, были относительно легкими, грамматически; взлом парсера был не слишком сложным - именно семантический анализ был медведем для лямбда.

Редкие неприятные проблемы в грамматике С#, если смотреть вперёд, - это generics и cast.

В С# 2 добавлены дженерики, после того, как в языке уже были операторы >>, > и <, все из которых могут вызывать странные проблемы при бросании дженериков в микс.

Классическая проблема, конечно, A ( B < C, D> ( E ) ) Использует ли вызов метода A два аргумента: B < C и D > (E) или один, B<c,d>( E )</c,d>?

Правило для устранения разногласий:

Если последовательность токенов может быть проанализирована как простое имя, член-доступ или конец доступа к указателю-члену с типом-аргументом-списком, проверяется токен, следующий за закрывающим маркером >. Если это один из ( ) ] : ; , . ? == !=, список типов-аргументов сохраняется как часть простого имени, доступа к члену или указателю-члену, а любой другой возможный синтаксический анализ последовательности токенов отбрасывается. В противном случае список аргументов типа не считается частью простого имени, доступа к члену или указателю-члену, даже если нет другого возможного анализа последовательности токенов.

Вторая проблема с грамматикой возвращается к С# 1.0 и к оператору литья. Проблема в том, что (x)-y может означать "cast -y для ввода x", или это может означать вычесть y из x. Правило здесь:

Последовательность одного или нескольких токенов, заключенных в круглые скобки, считается началом выражения-выражения только в том случае, если верно хотя бы одно из следующих значений:

Последовательность токенов - это правильная грамматика для типа, но не для выражения.

Последовательность токенов - это правильная грамматика для типа, а токен, следующий за закрывающимися скобками, - это токен "~", токен "!", токен "(", идентификатор, литерал или любое ключевое слово кроме as и is.

Правила, которые устраняют оба случая, предполагают потенциально большие перспективы в теории, но на практике вам очень редко приходится поддерживать парсер очень далеко.


Да, эта ситуация является прямым конфликтом сокращения/сокращения.

%token identifier ARROW
%%
program
: expression
| program expression
;
identifier_list
: identifier
| identifier_list identifier;
lambda_arguments
: '(' identifier_list ')'
| identifier;
lambda
: lambda_arguments ARROW expression;
primary_expression
: '(' expression ')'
| identifier
| lambda;
expression : primary_expression
$ yacc -v test.6.y 
conflicts: 1 reduce/reduce

Это точно из-за того, что вы не знаете, какое сокращение сделать, когда следующий символ ): мы уменьшаем список lambda_arguments или primary_expression?

Генератор синтаксического анализатора разрешил его неверно, в пользу списка лямбда. Но это означает, что выражение в скобках не может быть создано.

Из этого беспорядка есть несколько способов. Вот, наверное, самый простой подход - модифицированная грамматика, которая не содержит конфликтов:

%token identifier ARROW
%%
program
: expression
| program expression
;
identifier_list
: identifier
| identifier_list identifier
;
lambda_arguments
: '(' identifier identifier_list ')'
| identifier
;
primary_expression
: '(' expression ')'
| '(' expression ')' ARROW expression
| lambda_arguments ARROW expression
| identifier
;
expression : primary_expression

Мы сбрасываем синтаксис лямбда в primary_expression, а lambda_arguments теперь либо является единственным несвязанным идентификатором, либо списком по меньшей мере двух идентификаторов.

Кроме того, теперь для lambdas есть два синтаксических случая:

| '(' expression ')' ARROW expression
| lambda_arguments ARROW expression

Таким образом, должны быть написаны два правила семантического действия. Некоторая логика будет распространена, поэтому ее можно обработать вспомогательной функцией, которая строит дерево синтаксиса node для лямбда.

Действие для первого синтаксического варианта должно проверять правый символ $2 и проверять, что это простое первичное выражение, состоящее из токена идентификатора. Если это так, действие трещины открывает выражение, выдает идентификатор и строит лямбда-лист из этого идентификатора и использует этот список для генерации синтаксиса лямбда node, который заканчивается как выход правила ($$ значение в терминах Yacc). Если $2 - любой другой вид выражения, тогда выдается диагностика: это плохой синтаксис лямбда, например ( 2 + 2 ) => foo. Разумеется, это было принято парсером, каким образом было вызвано правило. Но теперь это семантически отвергается (где семантически относится к низкокалорийной версии слова "семантика" ).

Действие для второго варианта прост: возьмите лямбда-список, выражение тела и сделайте лямбда node, как раньше.

Проще говоря, синтаксис лямбда настолько тесно интегрирован в синтаксис выражений, что он не может быть легко скомпилирован в полностью отдельные правила, которые приводятся через единое производство, которое требует, чтобы lambda сокращалось до primary_expression. Это желаемое за действительное, потому что правила для парсера с уменьшением сдвига не являются функциональными вызовами.


Я не думаю, что вопрос грамматики лямбда-выражения интересен сам по себе, если не известно, что остальная часть языка LALR (1).

Если вы хотите узнать ответ, подайте свою подграмму в парсер LALR (1) генератор. Если он жалуется на конфликты с уменьшением или уменьшением сокращения, это не ЛАЛР (1). Является ли грамматика ЛАЛР (1), определяется ли вы можете построить для него таблицы перехода по определению.

В основном требуется парсер для всего языка.

Здесь есть два интересных вопроса.

1) Является ли С# 4.5 как язык LALR (1) вообще? (например, существует ли какая-либо грамматика, которая является LALR (1)? Обратите внимание, что конкретная грамматика, не являющаяся LALR (1), не означает, что другой не существует.

2) Являются ли какие-либо из CML-грамматик, опубликованных Microsoft (в его многочисленных формах) LALR (1)?

Я думаю, что Эрик сказал нам, что 1) не соответствует действительности. Это говорит о 2) также неверно.

С++ требует бесконечного поиска для разрешения своих шаблонов, вызванного в основном локальными возможностями " > ", которые интерпретируются как "end template args" или "больше". Поскольку С# скопировал это, я ожидаю, что он также будет иметь бесконечные требования к представлению на разрешение шаблона. Это определенно не LALR (1). [Там дополнительный беспорядок что " → " можно рассматривать как оператор сдвига, а " → " не может, что вы не можете исправить в грамматике, потому что он не может видеть пробелы.]

Моя компания использует GLR для своих инструментов обработки языка, и у нас есть грамматика С# 4.5, которая работает отлично. GLR означает, что нам не нужно думать о том, как преобразовать контекстно-свободную грамматику в совместимую с LALR (1) форму (например, изгиб, твист, фактор влево/вправо, перетасовку) или код ad hoc look ahead и т.д. и поэтому мы можем сосредоточиться на проблемах обработки кода, а не на синтаксическом анализе.

Это означает, что касты и другие конструкции создают неоднозначные деревья во время разбора, но они легко разрешаются, если у вас есть информация о типе.

licensed under cc by-sa 3.0 with attribution.