Манипулирование следующие грамматику быть LL (1)

Пусть я получил следующую грамматику:Манипулирование следующие грамматику быть LL (1)

start -> statement //cannot change 

statement -> assignment SEMICOLON 

statement -> function_call SEMICOLON 

assignment -> IDENTIFIER EQUAL expression 

function_call -> IDENTIFIER LPAREN parameters RPAREN SEMICOLON

Грамматика теперь не может быть LL (1), так как не являющиеся терминалы для заявления (назначение и function_call) оба имеют IDENTIFIER как первый терминал для каждого из их производства. Только с помощью 2 взглянуть вперед вы можете решить, какой путь будет принимать парсер.

Есть ли способ манипулировать грамматикой выше, чтобы быть LL (1)? Или это невозможно?

источник

2016-10-20 BDillan

Левый факторинг должен быть легко найти. Подсказка: 'statement: IDENTIFIER rest; отдых: что-то | something-else' – rici

@rici Я понимаю, но если у вас есть что-то вроде [statement -> compound_statement] и [compound_statement -> назначение | function_call] все еще будет считаться LL (1)? – BDillan

нет, это не так. Чтобы быть LL (1), вам нужно знать, какое производство будет расширено, если посмотреть на следующие (1) токены. Следующий токен будет IDENTIFIER, и это позволит вам предсказать 'statement -> composite_statement', но не какое из двух' составных_производств'. Таким образом, вам нужно левого фактора или выбрать более мощный алгоритм синтаксического анализа, например LR (1). – rici

Грамматика выше на самом деле не LL (к) при любом к, но мы можем построить LL (1) грамматики для того же языка:

start -> statement // cannot change 

statement -> IDENTIFIER statement0 SEMICOLON 

statement0 -> EQUAL expression 

statement0 -> LPAREN parameters RPAREN SEMICOLON

Конечно, в описании проблемы, мы не делаем см. определение выражения и параметров, поэтому мы предполагаем, что мы также можем построить для них правила LL (1) (что не гарантируется, пока мы не увидим правила).

источник

2016-11-03 06:55:02 Slava

Манипулирование следующие грамматику быть LL (1)

ответ

Смежные вопросы