Проблемы с грамматикой LL (1)

У меня есть 26 правил грамматики для субграмматики Mini Java. Предполагается, что эта грамматика не является объектно-ориентированной. Во всяком случае, я пытался левого фактора и удалить левую рекурсию. Однако я тестирую его с помощью JFLAP, но он говорит мне, что это не LL (1). Я следовал за каждым шагом алгоритма в книге Ахо-Сетхи.Проблемы с грамматикой LL (1)

Не могли бы вы дать мне несколько советов?

Goal ::= MainClass $ 
MainClass ::= class <IDENTIFIER> { MethodDeclarations public static void main () { 
    VarDeclarations Statements } } 
    VarDeclarations ::= VarDeclaration VarDeclarations | e 
VarDeclaration ::= Type <IDENTIFIER> ; 
MethodDeclarations ::= MethodDeclaration MethodDeclarations | e 
MethodDeclaration ::= public static Type <IDENTIFIER> (Parameters) { 
    VarDeclarations Statements return GenExpression ; } 
Parameters ::= Type <IDENTIFIER> Parameter | e 
Parameter ::= , Type <IDENTIFIER> Parameter | e 
Type ::= boolean | int 
Statements ::= Statement Statements | e 
Statement ::= { Statements } 
     | if (GenExpression) Statement else Statement 
     | while (GenExpression) Statement 
     | System.out.println (GenExpression) ; 
     | <IDENTIFIER> = GenExpression ; 
GenExpression ::= Expression | RelExpression 
Expression ::= Term ExpressionRest 
ExpressionRest ::= e | + Term ExpressionRest | - Term ExpressionRest 
Term ::= Factor TermRest 
TermRest ::= e | * Factor TermRest 
Factor ::= (Expression) 
     | true 
     | false 
     | <INTEGER-LITERAL> 
     | <IDENTIFIER> ArgumentList 
ArgumentList ::= e | (Arguments) 
RelExpression ::= RelTerm RelExpressionRest 
RelExpressionRest ::= e | && RelTerm RelExpressionEnd 
RelExpressionEnd ::= e | RelExpressionRest 
RelTerm ::= Term RelTermRest 
RelTermRest ::= == Expression | < Expression | ExpressionRest RelTermEnding 
RelTermEnding ::= == Expression | < Expression 
Arguments ::= Expression Argument | RelExpression Argument | e 
Argument ::= , GenExpression Argument | e

Каждый <IDENTIFIER> является допустимым идентификатором Java и <INTEGER-LITERAL> является простым числом. Каждое производство e означает эпсилон, а в первом правиле $ является маркером конца файла.

источник

2012-06-30 Milad Naseri

Я думаю, что я заметил две проблемы (там может быть больше):

Проблема № 1

В MainClass у вас есть

MethodDeclarations public static void main

И MethodDeclaration является

public static Type | e

Это не LL (1), так как синтаксический анализатор видит «публичный», он не может определить, является ли это MethodDeclaration или "public static void main".

Проблема № 2

Arguments ::= Expression Argument | RelExpression Argument | e

Оба выражения:

Expression ::= Term ExpressionRest

... и RelExpression:

RelExpression ::= RelTerm RelExpressionRest 
RelTerm ::= Term RelTermRest

... начать с "Term", так что это не LL (1).

Я бы просто пошел за LL (k) или LL (*), потому что они позволяют вам писать гораздо более удобные грамматики.

источник

2012-06-30 22:04:25 stmax

Спасибо. Ну, это два, и я думаю, что их больше. Разве нет методического способа проверить эти лазейки? –

Самый быстрый и надежный способ, вероятно, состоит в том, чтобы позволить вашему генератору парсеров выполнить проверку состояния LL (1). Проверка этого в основном требует, чтобы вы определили все терминальные символы, с которых может начинаться каждое правило. Вы знаете, что это не LL (1), если некоторые правила правила начинаются с одних и тех же терминальных символов. Это почти то же самое, что и ваш генератор парсера, и то, что я делал, глядя на вашу грамматику. Вы получите хорошее представление об этом после работы с грамматиками на некоторое время, но, конечно же, спросите генератор синтаксического анализатора. – stmax

Статья в Википедии о [Построение таблицы разбора LL (1)] (http: // ru. wikipedia.org/wiki/LL_parser#Constructing_an_LL.281.29_parsing_table) содержит подробное описание этого метода.Последнее предложение важно: «Если таблица содержит не более одного правила в каждой из своих ячеек, тогда синтаксический анализатор всегда будет знать, какое правило он должен использовать, и поэтому может анализировать строки без обратного отслеживания **. Именно в этом случае что грамматика называется грамматикой LL (1). ** " – stmax

Есть ли что-нибудь, что помешало бы IDENTIFIER быть таким же, как одно из ваших зарезервированных слов? если нет, то ваша грамматика будет неоднозначной. Я не вижу ничего другого.

Если все остальное не удается, я удаляю все, кроме последней строки грамматики, и проверю это. Если это пройдет, я добавлю каждую строку по одному, пока не найду проблемную строку.

источник

2012-06-30 20:19:27 ams

IDENTIFIER гарантирует, что не будет ключевое слово. Предположите, что это {все слова, не начинающиеся с числа} - {ключевые слова Java}. –

ответ

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