查看“Left-recursion.md”的源代码
←
Left-recursion.md
跳到导航
跳到搜索
因为以下原因,您没有权限编辑本页:
您请求的操作仅限属于该用户组的用户执行:
用户
您可以查看和复制此页面的源代码。
{{MARKDOWN}} # Left-recursive rules(左递归规则) 一些通用语言构造的最自然的表达是左递归。 例如C声明符和算术表达式。 不幸的是,算术表达式的左递归规范通常是模棱两可的,但比典型的自上而下语法所需的多级更容易写出。 这里是一个带有左递归表达式规则的示例ANTLR 4语法: ``` stat: expr '=' expr ';' // e.g., x=y; or x=f(x); | expr ';' // e.g., f(x); or f(g(x)); ; expr: expr '*' expr | expr '+' expr | expr '(' expr ')' // f(x) | id ; ``` 在直接上下文无关语法中,这样的规则是不明确的,因为1+2*3`可以将任一运算符解释为优先, 但ANTLR使用语义谓词将其重写为非左递归和明确化: ``` expr[int pr] : id ( {4 >= $pr}? '*' expr[5] | {3 >= $pr}? '+' expr[4] | {2 >= $pr}? '(' expr[0] ')' )* ; ``` 谓词通过将当前运算符的优先级与先前运算符的优先级进行比较来解决歧义。 expr[pr]的扩展只能匹配优先级满足或超过pr的子表达式。 ## Formal rules(正则规则) 正则4.0,4.1 ANTLR左递归消除规则被更改 (简化) 为4.2,并在 [所有 (*) 技术报告] 中列出 (http://www.antlr.org/papers/allstar-techreport.pdf): * Binary表达式是包含规则递归调用的表达式,该规则是可选的第一个和最后一个元素。 * Suffix表达式包含将规则递归调用作为备选方案的第一个元素,但不包含作为最后一个元素。 * Prefix 表达式包含规则的递归调用,作为替代方案的最后一个元素,但不作为第一个元素。 没有“三元”表达式——它们只是伪装的二进制表达式。 right associativity specifiers(右关联)过去用在单个Token上;但是无论如何它是在alternative基础上进行的,所以现在可选择用在单个alternative上;例如, ``` e : e '*' e | e '+' e |<assoc=right> e '?' e ':' e |<assoc=right> e '=' e | INT ; ``` 如果您的4.0或4.1语法使用右关联三元运算符,则需要更新语法以在alternative运算符上包含 `<assoc=right>`”。 为了平滑过渡,Token引用仍然允许使用`<assoc=right>`,但它只是被忽略。
返回至“
Left-recursion.md
”。
导航菜单
个人工具
登录
命名空间
页面
讨论
变体
已展开
已折叠
查看
阅读
查看源代码
查看历史
更多
已展开
已折叠
搜索
导航
首页
最近更改
随机页面
MediaWiki帮助
工具
链入页面
相关更改
特殊页面
页面信息