Грамматика: как добавить уровень приоритета - PullRequest
Новая
       74

Грамматика: как добавить уровень приоритета

2 голосов
/ 07 мая 2020

Допустим, у меня есть следующая контекстно-свободная грамматика для простого языка калькулятора: 

S->TS'
S'->OP1 TE'|e
T->FT'
T'->OP2 FT'|e
F->id|(S)
OP1->+|-
OP2->*|/

Как видно, * и / имеют более высокий приоритет над + и -. Однако как я могу добавить еще один уровень приоритета? Примером может быть показатель степени, ^, (например, 3 ^ 2 = 9) или что-то еще? Пожалуйста, объясните свою процедуру и причины того, как вы туда попали, чтобы я мог сделать это для других операторов.

1 Ответ

2 голосов
/ 08 мая 2020

Вот более удобочитаемая грамматика: 

expr: sum

sum : sum add_op term
    | term

term: term mul_op factor
    | factor

factor: ID
      | '(' expr ')'

add_op: '+' | '-'
mul_op: '*' | '/'

Это можно легко расширить, используя тот же шаблон: 

expr: bool

bool: bool or_op conj
    | conj

conj: conj and_op comp
    | comp

/* This one doesn't allow associativity. No a < b < c in this language */ 
comp: sum comp_op sum

sum : sum add_op term
    | term

term: term mul_op factor
    | factor

/* Here we'll add an even higher precedence operators */
/* Unlike the other operators, though, this one is right associative */
factor: atom exp_op factor
    | atom

atom: ID
    | '(' expr ')'

/* I left out the operator definitions. I hope they are obvious. If not,
 * let me know and I'll put them back in
 */

Надеюсь, здесь шаблон более или менее очевиден.

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

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

foo: foo foo_op bar
   | bar

и переворачиваем его так, чтобы он был правильно ассоциативным: 

foo: bar foo_op foo
   | bar

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

Затем нам нужно использовать левый фактор, потому что анализ LL требует, чтобы каждая альтернатива для нетерминала имела уникальный префикс: 

foo : bar foo'
foo': foo_op foo
    | ε

Выполнение этого с каждым описанным выше рекурсивным продуктом (то есть для всех, кроме expr, comp и atom) даст грамматику, похожую на ту, с которой вы начали, только с большим количеством операторов.

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

term: term mul_op factor
    | factor

, в ней говорится, что term (или произведение, если хотите) не может быть правым аргументом умножения, но может быть левый аргумент. Это также говорит о том, что если вы находитесь в точке, в которой продукт будет действительным, вам действительно не нужно что-то с оператором умножения; вместо этого вы можете использовать factor. Но очевидно, что вы не можете использовать сумму, поскольку factor не анализирует выражения с помощью оператора суммы. (Он анализирует все, что находится внутри круглых скобок. Но это вещи внутри скобок.)

В этом смысле и ассоциативность, и приоритет неявны в грамматике.

...