Неявный приоритет

Question

Я читаю книгу «Flex and Bison», чтобы понять, как работают генераторы парсеров, и есть пример:

calclist: /* nothing */
        | calclist exp EOL { printf("= %d\n", $1); }
        ;

exp: factor
   | exp ADD factor { $$ = $1 + $3; } 
   | exp SUB factor { $$ = $1 - $3; }
   ;

factor: term
      | factor MUL term { $$ = $1 * $3; } 
      | factor DIV term { $$ = $1 / $3; }
      ;

term: NUMBER
    | ABS term { $$ = $2 >= 0? $2 : - $2; }
    ;

и в книге говорится, что приведенная выше грамматика имеет неявный приоритет за счет использования отдельных нетерминальных символов.Но как это работает?Предположим, у нас есть следующий пример: 1 + 3 * 2 (пробелы просто пропускаются) читаем первый токен 1 он будет помещен в стек как NUMBER или как term или как factor как долго оно будет «бурлить» в грамматике?Из какого грамматического правила будет проверяться следующий токен?Почему в этой грамматике умножение имеет более высокий приоритет, чем сложение?

Answer 1

Причина, по которой это имеет «неявный» приоритет (а не явный), действительно, как сказано в тексте, связана с факторизованной грамматикой (отдельные нетерминалы).

Проработайте свой пример 1 + 3 * 2, представляя себя компьютером, выполняющим синтаксический анализ, как бы следуя каждой инструкции «до буквы».Чтобы найти «exp» (выражение), вам нужно сначала найти фактор.(Другой вариант — начать с поиска «опыта», но для этого нужно найти «фактор».) Итак, вы должны найти фактор…но для этого вам необходимо найти «термин», потому что фактор — это либо термин, либо фактор, который сам начинается с термина.Итак, теперь вам нужно найти термин, который является либо NUMBER или ключевое слово ABS.Таким образом, вы можете «принять» (в терминах грамматики) 1, что по сути является NUMBER, и вы преуспели в первой части анализа — поиске термина.(Теперь вы удалите 1 из потока токенов, оставляя вас с + в качестве следующего токена.)

Теперь, когда у вас есть термин, у вас также есть фактор (по определению), но для того, чтобы «завершить действие наличия фактора», вам необходимо попытаться найти более длинное совпадение:фактор, за которым следует MUL или DIV, за которым следует что-то.Ваш следующий жетон +:это не MUL и не DIV.Таким образом, вы вынуждены прекратить анализ фактора и вернуть всю цепочку анализа, вплоть до вашего фактора: 1 является фактором, и следующий токен по-прежнему +.

Теперь, когда у вас есть фактор, у вас есть опыт (по определению), но чтобы «завершить действие получения опыта», вам снова необходимо попытаться найти более длинное совпадение:опыт, за которым следует ADD или SUB, за которым следует что-то.Следующий жетон все еще + что по сути является ДОБАВКОЙ...поэтому вы должны продолжить exp ADD factor { $$ = $1 + $3 }; правило.

На этом этапе вы (как анализатор) помещаете все это в стек и снова приступаете к работе в поисках подходящего нетерминала - в данном случае еще одного «фактора».Итак, теперь вы начинаете с правила для фактора.Вы должны искать «термин», и если вы его найдете, попробуйте выполнить более длинную версию правила, включающую MUL или DIV.Проработав эту часть, вы увидите, что * токен действительно является MUL, и вам придется принять более длинное правило, заставив результат «фактора» использовать factor MUL term { $$ = $1 * $3; } часть правила.Это позволит принять, то есть съесть/израсходовать, 3 * 2 последовательность и вернуть значение 6 для «фактора», который позволяет вам завершить правило, которое вы поместили в свой стек синтаксического анализа.

Вернувшись в состояние push, вы завершаете анализ «1 +», добавляя 1 и принимая (съедая) полное выражение.И, конечно же, 1 + 6 равно 7, так что ваша грамматика возвращает правильное значение.

Answer 2

Приоритет является результатом того, что операнды ADD и SUB являются факторами, и только факторы содержат операторы MUL и DIV.ADD не конкурирует с MUL, поскольку MUL инкапсулирован в термин.

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

Данный A + X * Y, X * Y выражение сводится к term который представляет собой единый грамматический символ, который больше не выражает * оператор, и поэтому нет ничего для + оператор, против которого возникает проблема приоритета;это сейчас просто A + term.

Кстати, в грамматике используется нетрадиционная перевернутая терминология.

Это термины:А + Б + С

Это факторы:А*Б*С

Члены складываются («члены ряда»), коэффициенты умножаются («множители целого числа или многочлена»).

Это действительно из этого учебника?В любом случае попробуйте Составители:Принципы, методы и инструменты Ахо, Сети, Ульман.(1988 год, но классика).