LL1 грамматика для арифметических выражений и заданий - PullRequest
Новая
       72

LL1 грамматика для арифметических выражений и заданий

0 голосов
/ 10 ноября 2018

Я хотел бы разработать грамматику LL1 для арифметических уравнений и присвоений переменных.Я начал с этой грамматики:

У меня есть однозначная грамматика для арифметических выражений: 

E → T E’
E’ →  | + E
T → id T’
T’ →  | * T

Однако я не уверен, как включить присваивания переменных в E-произведения.

Как я пробовал ранее было: 

    stmt -> assignment SEMI | RETURN stmt_prime 
   | LBRACE stmt_list RBRACE 
   | IF LPAREN assignment RPAREN stmt stmt_prime_prime 
   | FOR LPAREN assignment SEMI assignment SEMI assignment RPAREN stmt | 
    stmt_prime -> SEMI | -> assignment SEMI
    stmt_prime_prime -> NOELSE 
    | ELSE stmt
    assignment -> ID typ ASSIGN expr | expr  
    expr -> TE* 
    E* -> + TE* | -TE* | epsilon
    T -> FT*
    T* -> * FT* | / FT* | epsilon
    F -> (E) | int_literal | TRUE | FALSE

1 Ответ

0 голосов
/ 10 ноября 2018 
assignment -> ID ASSIGN expr | expr

(я игнорирую часть typ, потому что полагаю, что она попала туда случайно)

Проблема здесь в том, что и ID ASSIGN expr, и expr могли бы начинаться с ID (или, по крайней мере, могли бы, если бы T содержал ID в качестве опции, что, как я полагаю, было намерением), поэтому это не LL (1). Однако это LL (2), поэтому, если вы в порядке с этим, вы можете просто добавить andalso next_token = ASSIGN к условию if в вашем анализаторе и покончить с этим.

Если вам нужно, чтобы это был LL (1), вам придется настроить язык, разрешенный вашим парсером, я боюсь (то есть, нет грамматики LL (1), которая точно соответствует тому же языку как ваша текущая грамматика). Одним из простых способов было бы просто добавить ключевое слово, например SET, до назначения, хотя, по общему признанию, это ужасно.

Другая альтернатива - разрешить произвольные выражения в качестве левого операнда =, что делает ваше правило присваивания: 

assignment -> exp (ASSIGN exp)?

Что такое LL (1). Недостатком этого является то, что он допускает много бессмысленного кода, такого как 1+2 := 42, но вы можете исправить это за пределами грамматики. То есть, ваш код для разбора назначений может просто вызвать parse_exp, а затем, если следующий токен - ASSIGN, а выражение, возвращаемое parse_exp - не просто идентификатор, выдает ошибку, что левая часть присвоение должно быть идентификатором.

...