添加 (...) {...} 函数文字同时避免回溯 [英] adding (...) {...} function literals while abstaining from backtracking

问题描述

建立在 如何在没有回溯的情况下同时进行函数调用和括号分组，我想添加非 LL(*) 表示实现的函数文字

Building off the answer found in How to have both function calls and parenthetical grouping without backtrack, I'd like to add function literals which are in a non LL(*) means implemented like

...

tokens {
 ...
 FN;
 ID_LIST;
}

stmt
 : expr SEMI // SEMI=';'
 ;

callable
 : ...
 | fn
 ;

fn
 : OPAREN opt_id_list CPAREN compound_stmt
   -> ^(FN opt_id_list compound_stmt)
 ;

compound_stmt
 : OBRACE stmt* CBRACE

opt_id_list
 : (ID (COMMA ID)*)? -> ^(ID_LIST ID*)
 ;

<小时>

我想做的是允许具有参数列表的匿名函数文字(例如 () 或 (a) 或 (a, b, c)) 后跟一个 compound_stmt.所以 (a, b, c){...} 是好的.但 (x)(y){} 没有那么多.(当然 (x) * (y){} 就解析器而言是有效的"，就像 ((y){})()[1].x代码> 将是.)

---

What I'd like to do is allow anonymous function literals that have an argument list (e.g. () or (a) or (a, b, c)) followed by a compound_stmt. So (a, b, c){...} is good. But (x)(y){} not so much. (Of course (x) * (y){} is "valid" in terms of the parser, just as ((y){})()[1].x would be.)

推荐答案

解析器需要一些额外的前瞻性.我想它可以在没有它的情况下完成，但它肯定会导致一些看起来很糟糕的解析器规则，这些规则很难维护 和 一个接受 (a, 2,3){...}(带有表达式列表而不是 id 列表的函数文字)，例如.这将导致您在创建 AST 后进行大量语义检查.

The parser needs a bit of extra look ahead. I guess it could be done without it, but it would definitely result in some horrible looking parser rule(s) that are a pain to maintain and a parser that would accept (a, 2, 3){...} (a function literal with an expression-list instead of an id-list), for example. This would cause you to do quite a bit of semantic checking after the AST has been created.

(IMO)解决这个问题的最好方法是在 callable 中添加 function literal 规则并在它前面添加一个句法谓词，它会告诉解析器在实际匹配之前确保真的有这样的选择.

The (IMO) best way to solve this is by adding the function literal rule in the callable and adding a syntactic predicate in front of it which will tell the parser to make sure there really is such an alternative before actually matching it.

callable
 : (fn_literal)=> fn_literal
 | OPAREN expr CPAREN -> expr
 | ID
 ;

演示:

grammar T;

options {
  output=AST;
}

tokens {
 // literal tokens
 EQ     = '==' ;
 GT     = '>' ;
 LT     = '<' ;
 GTE    = '>=' ;
 LTE    = '<=' ;
 LAND   = '&&' ;
 LOR    = '||' ;
 PLUS   = '+' ;
 MINUS  = '-' ;
 TIMES  = '*' ;
 DIVIDE = '/' ;
 OPAREN = '(' ;
 CPAREN = ')' ;
 OBRACK = '[' ;
 CBRACK = ']' ;
 DOT    = '.' ;
 COMMA  = ',' ;
 OBRACE = '{' ;
 CBRACE = '}' ;
 SEMI   = ';' ;

 // imaginary tokens
 CALL;
 INDEX;
 LOOKUP;
 UNARY_MINUS;
 PARAMS;
 FN;
 ID_LIST;
 STATS;
}

prog
 : expr EOF -> expr
 ;

expr
 : boolExpr
 ;

boolExpr
 : relExpr ((LAND | LOR)^ relExpr)?
 ;

relExpr
 : (a=addExpr -> $a) ( (oa=relOp b=addExpr    -> ^($oa $a $b))
                         ( ob=relOp c=addExpr -> ^(LAND ^($oa $a $b) ^($ob $b $c))
                         )?
                     )?
 ;

addExpr
 : mulExpr ((PLUS | MINUS)^ mulExpr)*
 ;

mulExpr
 : unaryExpr ((TIMES | DIVIDE)^ unaryExpr)*
 ;

unaryExpr
 : MINUS atomExpr -> ^(UNARY_MINUS atomExpr)
 | atomExpr
 ;

atomExpr
 : INT
 | call
 ;

call
 : (callable -> callable) ( OPAREN params CPAREN -> ^(CALL $call params)
                          | OBRACK expr CBRACK   -> ^(INDEX $call expr)
                          | DOT ID               -> ^(INDEX $call ID)
                          )*
 ;

callable
 : (fn_literal)=> fn_literal
 | OPAREN expr CPAREN -> expr
 | ID
 ;

fn_literal
 : OPAREN id_list CPAREN compound_stmt -> ^(FN id_list compound_stmt)
 ;

id_list
 : (ID (COMMA ID)*)? -> ^(ID_LIST ID*)
 ;

params
 : (expr (COMMA expr)*)? -> ^(PARAMS expr*)
 ;

compound_stmt
 : OBRACE stmt* CBRACE -> ^(STATS stmt*)
 ;

stmt
 : expr SEMI
 ;

relOp
 : EQ | GT | LT | GTE | LTE
 ;

ID     : 'a'..'z'+ ;
INT    : '0'..'9'+ ;
SPACE  : (' ' | '\t') {skip();};

由上述语法生成的解析器会拒绝输入(x)(y){}，但它会正确解析以下 3 段代码:

A parser generated by the grammar above would reject the input (x)(y){} while it properly parses the following 3 snippets of code:

(a, b, c){ a+b*c;}

(x) * (y){ x.y;}

((y){})()[1].x

这篇关于添加 (...) {...} 函数文字同时避免回溯的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！