Устранить левую рекурсию для моей грамматики

Question

Можете ли вы помочь мне в этом примере? Как я должен удалить исключение рекурсии с этим размером? Я знаю, как это сделать для более простых примеров.

Expr1  ::= Number 
    | String 
    | `true` 
    | `false` 
    | `undefined`    
    | Expr1 `+` Expr1    
    | Expr1 `-` Expr1    
    | Expr1 `*` Expr1    
    | Expr1 `%` Expr1    
    | Expr1 `<` Expr1    
    | Expr1 `===` Expr1    
    | Ident AfterIdent    
    | `[` Exprs `]`   
    | `[` `for` `(` Ident `of` Expr `)` ArrayCompr Expr `]`    
    | `(` Expr `)` 

Это решение?

Expr1  ::= Number ExprB  
    | String ExprB  
    | `true` ExprB  
    | `false` ExprB  
    | `undefined` ExprB      
    | Ident AfterIdent ExprB   
    | `[` Exprs `]`    
    | `[` `for` `(` Ident `of` Expr `)` ArrayCompr Expr `]`    
    | `(` Expr `)` 
ExprB  ::= ϵ 
    | `+` Expr1 ExprB 
    | `-` Expr1 ExprB 
    | `*` Expr1 ExprB 
    | `%` Expr1 ExprB 
    | `<` Expr1 ExprB 
    | `===` Expr1 ExprB 

Answer 1

Трюк, который я узнал, заключается в том, чтобы вводить конструктивные нетерминалы, чтобы получить меньшее количество правил грамматики в любом месте. У вас все еще есть некоторые неприятные расширения, присущие языку, но вы можете сделать процесс проще на каждом шаге.

Scalar ::= Number | String | `true` | `false` | `undefined` 
Op  ::= '+' | '-' | '*' | '%' | '<' | '===' 
OpExpr ::= Expr1 Op Expr1 
ParenExpr ::= 
     `[` Exprs `]` 
    | `[` `for` `(` Ident `of` Expr `)` ArrayCompr Expr `]` 
    | `(` Expr `)` 

Expr1 ::= 
     Scalar 
    | OpExpr 
    | ParenExpr 
    | Ident AfterIdent 

Здесь есть два основных преимущества. Во-первых, если вы используете парсер, правила теперь более точно соответствуют семействам обработки. Вы можете принять определенные общие меры при классифицированных сокращениях. Во-вторых, вы можете упростить устранение рекурсии: у вас есть такое же количество терминалов, чтобы начать Expr1, но только одно правило для расширения - определение OpExpr.

Я знаю, что я не выполнил упражнение для вас, но я надеюсь, что это поможет вам добиться успеха. Вы также можете проверить грамматики приоритета операторов: они обрабатывают некоторые из них элегантным способом, в зависимости от вашего приложения.