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

У меня есть грамматика из 26 правил для подграмматики Mini Java. Предполагается, что эта грамматика не является объектно-ориентированной. Во всяком случае, я пытался сделать это с помощью левого фактора и удалить левую рекурсию. Однако я тестирую его с помощью JFLAP, но он говорит мне, что это не 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 обозначает продукцию эпсилон, а $ в первом правиле является маркером конца файла.


parsing grammar ll left-recursion ambiguity
person Milad Naseri    schedule 30.06.2012    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

Проблема №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

... начните с «Термин», так что это тоже не LL (1).

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

person stmax    schedule 30.06.2012
comment
Спасибо. Ну, это два, и я думаю, что есть еще. Нет ли методического способа проверить эти лазейки? - person Milad Naseri; 01.07.2012
comment
Самый быстрый и надежный способ, вероятно, состоит в том, чтобы позволить вашему генератору синтаксического анализатора выполнять проверки условий LL(1). Чтобы проверить это самостоятельно, в основном требуется, чтобы вы выяснили все терминальные символы, с которых может начинаться каждое правило. Вы знаете, что это не LL(1), если некоторые условия правила начинаются с одинаковых терминальных символов. Это почти то же самое, что делает ваш генератор синтаксических анализаторов, и то, что я сделал, просматривая вашу грамматику. Вы почувствуете это после того, как некоторое время поработаете с грамматиками, но для уверенности спросите у генератора парсеров :) - person stmax; 01.07.2012
comment
В статье Википедии Построение таблицы синтаксического анализа LL(1) содержится подробная описание этого метода. Последнее предложение важно: если таблица содержит не более одного правила в каждой из своих ячеек, то синтаксический анализатор всегда будет знать, какое правило он должен использовать, и, следовательно, может анализировать строки без возврата. Именно в этом случае грамматика называется LL(1)-грамматикой. - person stmax; 01.07.2012
comment
Спасибо. Я сделаю это. Я знаю, что нет точного «ответа» на такого рода вопросы, поэтому я приму ваш и буду больше над ним работать. - person Milad Naseri; 01.07.2012
comment
В конце концов, я использовал ANTLRWorks, чтобы исправить грамматику и сгенерировать правильный синтаксический анализатор, хотя результатом был не LL(1), а скорее LL(*). - person Milad Naseri; 15.07.2012

arrow_upward
0
arrow_downward

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

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

person ams    schedule 30.06.2012
comment
IDENTIFIER гарантированно не является ключевым словом. Считайте, что это {все слова, не начинающиеся с цифры} - ​​{ключевые слова Java}. - person Milad Naseri; 01.07.2012