Неявный приоритет - PullRequest
Новая
       29

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

1 голос
/ 11 марта 2012

Я читаю книгу "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, как долго это будет "пузыриться" через грамматику? Из какого правила грамматики будет проверен следующий токен? Почему с этим грамматическим умножением более высокий приоритет, чем сложением?

Ответы [ 2 ]

2 голосов
/ 11 марта 2012

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

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

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

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

Это термины: A + B + C

Это факторы: A * B * C

Добавлены термины («члены ряда»), множители умножены («факторы целого или полинома»).

Это действительно из этого учебника? В любом случае, попробуйте Компиляторы: принципы, методы и инструменты от Aho, Sethi, Ullman. (1988, но классика).

2 голосов
/ 11 марта 2012

Причина, по которой это имеет «неявный» приоритет (а не явный), действительно такова, как говорится в тексте, из-за факторизованной грамматики (отдельных нетерминалов).представьте себя компьютером, выполняющим синтаксический анализ, следуя каждой инструкции «на букву».Чтобы найти «выражение» (выражение), вы должны сначала найти фактор.(Ваши другие варианты - начать с поиска «опыта», но для этого нужно найти «фактор».) Поэтому вы должны найти фактор ... но для этого вы должны найти «термин», потому что фактор - это либотермин, или фактор, который сам начинается с термина.Итак, теперь вы должны найти термин, который является либо 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, так что ваша грамматика возвращает правильное значение.

...