Создание свободных грамматик смещения / уменьшения / уменьшения - PullRequest
Новая
       40

Создание свободных грамматик смещения / уменьшения / уменьшения

0 голосов
/ 12 апреля 2011

Я пытаюсь реализовать простой синтаксический анализатор языка, подобный Java, в sablecc, хотя постоянно сталкиваюсь с проблемами shift-reduce / reduce-reduce при реализации операторов if, while и block.

Например, я рассмотрел следующее:

stmts = stmt*;

stmt = if_stmt |block_stmt |while_stmt;

block_stmt = { stmts } |;;

while_stmt = while ( predicate ) { stmts } |while ( predicate ) ;

Эта грамматика, например, вызовет проблему, когда у вас есть что-то вида 

while (true) ;

синтаксический анализатор не сможет узнать, нужно ли уменьшить только ; (с block_stmt) или полное while (true); (с while_stmt).

Я везде читал о причинахshift-reduce / reduce-reduce проблемы, и я думаю, что понимаю их.Но одно дело - знать, что их вызывает, а другое - знать, как структурировать грамматики так, чтобы я их избегал.Я попытался реализовать грамматику совершенно по-разному, и тем не менее у меня возникли проблемы.

Полагаю, что вместо того, чтобы просто пытаться запустить конкретную проблему ss / rr, должен быть видпарадигма, чтобы следовать такому, чтобы избежать такого рода проблем?Я считаю, что мой подход к проблеме должен быть совершенно неправильным: (

Есть ли какие-либо ресурсы о том, как создать грамматику с нуля, не попадая во все эти ловушки? Ресурсы по этому вопросу, как правило, либо очень просты (с указанием очевидной проблемы if then else) или полностью помеченных грамматик, которые являются своего рода непроницаемыми.

1 Ответ

2 голосов
/ 12 апреля 2011

Проблема в том, что ваша грамматика указана так, что, например, точка с запятой может интерпретироваться как точка с запятой в то время как while_stmt или точка в block_stmt ... нет, извините, не так, но как-то грамматика избыточна, потому что {stmt} появляется дважды в RHS,Обычно вы бы сделали 

 stmts ::= stmt | stmts stmt
 block_stmt ::= { stmts }
 stmt ::= ... | block_stmt | ;     // empty
 while_stmt ::= while ... stmt
...