Преобразовать форму грамматики BNF в грамматику g4 - PullRequest
Новая
       37

Преобразовать форму грамматики BNF в грамматику g4

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

Я пытаюсь скрыть эту грамматику BNF для проверки логического выражения, которое в настоящее время используется в Swift. Теперь хочу реализовать подобный парсер в Java. Я наткнулся на библиотеку Antlr4 и хочу использовать ее для генерации парсера для той же грамматики. Я не очень знаком с antlr4. Может кто-нибудь дать мне какое-нибудь руководство? Это то, что я имею до сих пор. 

Expr                ::= <ConcatenationExpr>;
NonInfixExpr        ::= <BracketExpr>
                      | <Function>
                      | <Literal>
                      | <Accessor>;
BracketExpr         ::= '(' <Expr> ')';
Accessor            ::= ('$' <AccessorComponent> | <AccessorComponent>) ('.' <AccessorComponent> )*;
AccessorComponent   ::= 'Identifier' ':' 'Identifier' | 'Identifier';
Function            ::= 'Identifier' '(' ')' | ('Identifier' '(' <Expr> (',' <Expr>)* ')');
Literal             ::= 'True'
                     | 'False'
                     | 'Null'
                     | 'Number'
                     | 'Text';
ConcatenationExpr   ::= <AndExpr>
                     | <ConcatenationExpr> '&' <AndExpr>;
AndExpr             ::= <OrExpr>
                     | <AndExpr> '&&' <OrExpr>;
OrExpr              ::= <EqualityExpr>
                     | <OrExpr> '||' <EqualityExpr>;
EqualityExpr        ::= <ComparisonExpr>
                     | <EqualityExpr> ('==' | '=' | '!=' | '<>') <ComparisonExpr>;
ComparisonExpr      ::= <AddExpr>
                     | <AddExpr> ('<' | '<=' | '>' | '>=') <AddExpr>;
AddExpr             ::= <ExponentialExpr>
                     | <AddExpr> ('+' | '-') <ExponentialExpr>;
ExponentialExpr     ::= <MultExpr>
                     | <ExponentialExpr> '^' <MultExpr>;
MultExpr            ::= <NonInfixExpr>
                     | <MultExpr> ('*' | '/') <NonInfixExpr>;

Я попытался преобразовать в g4, и вот как это выглядит. 

grammar VALIDATE;

Expr
    : ConcatenationExpr ';'
    ;

NonInfixExpr
    : BracketExpr 
    | Function 
    | Literal 
    | Accessor
    ;

BracketExpr 
    : '(' Expr ')'
    ;

Accessor
    : ('$' AccessorComponent | AccessorComponent ) ('.' AccessorComponent )*
    ;

AccessorComponent
    : 'Identifier' ':' 'Identifier' | 'Identifier'
    ;

Function
    : 'Identifier' '(' ')' | ('Identifier' '(' Expr (',' Expr)* ')')
    ;

Literal
    : 'True' | 'False' | 'Null' | 'Number' | 'Text'
    ;

ConcatenationExpr
    : AndExpr 
    | ConcatenationExpr '&&' AndExpr
    ;

AndExpr
    : OrExpr | AndExpr '&&' OrExpr
    ;

OrExpr
    : EqualityExpr | OrExpr '||' EqualityExpr
    ;

EqualityExpr
    : ComparisonExpr | EqualityExpr ('==' | '=' | '!=' | '<>') ComparisonExpr
    ;

ComparisonExpr
    : AddExpr | AddExpr ('<' | '<=' | '>' | '>=') AddExpr
    ;

AddExpr
    : ExponentialExpr | AddExpr ('+' | '-') ExponentialExpr
    ;

ExponentialExpr
    : MultExpr | ExponentialExpr '^' MultExpr
    ;

MultExpr
    : NonInfixExpr | MultExpr ('*' | '/') NonInfixExpr
    ;

Я застрял на шаге antlr4 VALIDATE.g4. Я не уверен, что правильно сделал преобразование. 

error(119): VALIDATE.g4::: The following sets of rules are mutually left-recursive [MultExpr] and [ExponentialExpr] and [AddExpr] and [EqualityExpr] and [OrExpr] and [AndExpr] and [ConcatenationExpr]
error(99): VALIDATE.g4::: grammar VALIDATE has no rules

1 Ответ

0 голосов
/ 12 января 2019

Исходная грамматика не имеет взаимной левой рекурсии - это было введено только в преобразованной версии с использованием && в ConcatenationExpr, где она должна была читать &. Как только это исправлено, грамматика имеет только прямую левую рекурсию, с которой ANTLR 4 должна справиться.

Вы можете даже полностью удалить левую рекурсию, переписав рекурсивные правила, например, такие как ConcatenationExpr станет 

ConcatenationExpr
     ::= AndExpr ( '&' AndExpr )*

Если это сделано для всех рекурсивных правил, результирующая грамматика будет LL (2).

...