На первый взгляд эквивалентные правила менгира изменяют конфликты сдвига / сокращения, встречающиеся в грамматике.

Я использую Menhir для создания синтаксического анализатора, и есть поведение, которое всегда сбивает меня с толку, и я его не понимаю. Я создал следующий минимальный пример, чтобы продемонстрировать это; это показывает объявление аргумента получателя в объявлении метода на языке Go (http://golang.org/ref/spec#Method_declarations):

%{

%}

%token <string> T_identifier
%token T_star

%start <unit> demo


%%


(* This rule has a shift/reduce conflict
demo:
| option(T_identifier) option(T_star) T_identifier { () } 
*)

(* This rule is okay. *)
demo:
| T_identifier T_star T_identifier { () }
| T_identifier T_identifier        { () }
| T_star T_identifier              { () }
| T_identifier                     { () }

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

Я смог продвинуться в своем синтаксическом анализаторе, заменив option несколькими правилами всякий раз, когда это происходило, но меня раздражало, что я не понимаю, почему это происходит.

(Если вы не знакомы с менгиром, то это генератор синтаксического анализатора LR(1), поэтому вам, вероятно, пригодится знание того, как работают другие подобные инструменты.)


parsing compiler-construction ocaml context-free-grammar menhir
person gnuvince    schedule 03.10.2014    source источник
comment
Вы хотите сказать, что демонстрационное правило само по себе приводит к конфликту SR? Или что это происходит в каком-то контексте?   -  person rici    schedule 04.10.2014
comment
Если вы скомпилируете код (menhir demo.mly), вы увидите, что в первом случае он жалуется на конфликт сдвига/уменьшения, но не во втором.   -  person gnuvince    schedule 04.10.2014

Ответы (2)


arrow_upward
4
arrow_downward

Я предполагаю, что Менгир сводит РБНФ к БНФ с помощью некоторых стандартных преобразований. Это довольно часто. К сожалению, эти преобразования могут подорвать разборчивость LR(1).

Рассмотрим ваше правило в другом синтаксисе, подобном EBNF:

demo → IDENTIFIER? STAR? IDENTIFIER

Один из способов перевести это в БНФ — это то, что вы делаете во втором наборе правил: определите четыре разных правила, по одному для каждой возможности. Это преобразование никогда не изменит разборчивость LR(1) и всегда возможно для правил с «необязательным» оператором, но у него есть два недостатка:

  1. Если в правиле есть несколько необязательных элементов, конечным результатом будет множество продукций.

  2. Это не работает для операторов повторения.

Другой способ, который кажется более общим, заключается в создании нового нетерминала для каждого расширенного оператора BNF. Итак, мы могли бы сделать это:

optional_identifier → IDENTIFIER | ε
optional_star       → STAR | ε
demo                → optional_identifier optional_star IDENTIFIER

Аналогичное преобразование будет работать для x*:

repeated_x → ε | repeated_x x

Это, безусловно, создает эквивалентный язык, но теперь грамматика может быть не LR(1).

В частности, demo больше не является LR(1). Он терпит неудачу в самом начале. Скажем, первый входной токен — IDENTIFIER. Это может быть началом

IDENTIFIER IDENTIFIER

or

IDENTIFIER

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

Во втором случае (просто тип) нам нужно уменьшить optional_identifier и optional_star, прежде чем мы сможем сдвинуть IDENTIFIER. В первом случае (переменная и тип) нам нужно сдвинуть IDENTIFIER сразу. И единственная информация, которая у нас есть, чтобы определить разницу, — это упреждающий токен IDENTIFIER, которого явно недостаточно.

Если мы используем четырехходовое расширенное производство, то проблем нет:

demo → IDENTIFIER
     | STAR IDENTIFIER
     | IDENTIFIER IDENTIFIER
     | IDENTIFIER STAR IDENTIFIER

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

Аналогичное явление происходит с yacc/bison и другими генераторами синтаксических анализаторов, которые допускают действия промежуточного правила (MRA). MRA превращается в новый не-терминал, единственным производством которого является производство; целью нового нетерминала является запуск MRA при его уменьшении. Это действительно здорово, за исключением того, что иногда новый нетерминал вводится в момент, когда мы не можем знать, уместно ли его уменьшить или нет. Таким образом, MRA может превратить совершенно хорошую LR(1)-грамматику в не-LR(1)-грамматику, даже если язык не изменился.

Хотя это и не имеет значения в случае Менгира, возможно, интересно, что приведенное выше преобразование РБНФ, если оно сделано аккуратно, не вносит двусмысленности, которой в противном случае не было бы. Таким образом, даже если результирующая грамматика больше не является LR(1), она по-прежнему недвусмысленна и может быть проанализирована парсером GLR. Однако, поскольку Menhir, насколько мне известно, не генерирует синтаксические анализаторы GLR, этот факт может оказаться не очень полезным.

person rici    schedule 04.10.2014

arrow_upward
1
arrow_downward

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

person ivg    schedule 03.10.2014