在龙书中,LL语法定义如下:
语法是LL,当且仅当适用于任何生产时A -> a|b,以下两个条件适用.
FIRST(a)并且FIRST(b)是不相交的.这意味着它们不能同时衍生出来EMPTY
如果b能够获得EMPTY,则a不能推导开头的任何字符串FOLLOW(A),就是FIRST(a)和FOLLOW(A)必须是不相交的.
我知道LL语法不能保持递归,但正式的原因是什么？我猜左递归语法会违反规则2,对吧？例如,我写了以下语法:
S->SA|empty
A->a
由于FIRST(SA) = {a, empty}和FOLLOW(S) ={$, a},然后FIRST(SA)和FOLLOW(S)不脱节,所以这个语法不是LL.但我不知道这是左递归FIRST(SA)而FOLLOW(S)不是不相交,还是有其他原因？换句话说,每个左递归语法都会产生违反LL语法条件2的情况吗？
我已经看到这个算法应该可以用来删除所有左递归.然而,我遇到了这个特殊语法的问题:
A -> Cd
B -> Ce
C -> A | B | f
无论我尝试什么,我最终都在循环中或使用仍然间接留下递归的语法.
在这个语法上正确实现这个算法的步骤是什么？
我一直在尝试用变量创建我的解析器表达式,并将它们简化为二次表达式.
这是我的解析器语法:
Exercise : Expr '=' Expr
Expr : Term [+-] Expr | Term
Term : Factor [*/] Term | Factor
Factor: Atom [^] Factor | Atom
Atom: Number | Identified | [- sqrt] Atom | '(' Expr ')'
对于解析我正在使用递归下降解析器.我想说我想解析一下:
"2 - 1 + 1 = 0"
结果为0,解析器创建错误的树:
-
/ \
2 +
/ \
1 1
我怎样才能使这个语法保持联想？我是新手,请你告诉我哪里可以找到更多信息？我可以用递归下降解析器实现这一点吗？
grammar parsing recursive-descent associativity left-recursion
我有一个小的自定义脚本语言,我试图更新它以允许布尔表达式,如a > 2和a > 2 and (b < 3 or c > 5).这是我在这里遇到麻烦的括号表达式.
这是一个(基于@Bart Kiers答案的原始帖子编辑后)完整语法,展示了这个问题.这是我实际语法的一个简化版本,但问题也出现在这里.
grammar test;
options {
language = 'JavaScript';
output = AST;
}
statement
: value_assignment_statement
EOF
;
value_assignment_statement
: IDENT
'='
expression
;
value_expression
: value_list_expression
| IDENT
;
value_list_expression
: value_enumerated_list
;
value_enumerated_list : '{' unary+ '}'
;
term
: LPAREN expression RPAREN
| INTEGER
| value_expression
;
unary : ( '+' | '-' )* term
;
mult : unary ( …在阅读C book中的Compiler Design时,我遇到了以下规则来描述无上下文语法:
识别一个或多个语句列表的语法,每个语句都是一个后跟分号的算术表达式.语句由一系列以分号分隔的表达式组成,每个表达式包含一系列由星号(用于乘法)或加号(用于加法)分隔的数字.
这是语法:
1. statements ::= expression;
2. | expression; statements
3. expression ::= expression + term
4. | term
5. term ::= term * factor
6. | factor
7. factor ::= number
8. | (expression)
该书指出这种递归语法存在一个主要问题.几个产品的右侧出现在生产3的左侧(并且此属性称为左递归),并且某些解析器(如递归下降解析器)无法处理左递归生成.他们只是永远地循环.
您可以通过考虑解析器在替换具有多个右侧的非终端时如何决定应用特定生产来理解该问题.简单的情况在制作7和8中很明显.解析器可以通过查看下一个输入符号来选择在扩展因子时应用哪个制作.如果此符号是数字,则编译器应用Production 7并用数字替换该因子.如果下一个输入符号是一个左括号,则解析器将使用Production 8.但是,Productions 5和6之间的选择无法以这种方式解决.在生产6的情况下,术语的右侧以一个因子开始,该因子以数字或左括号开始.因此,解析器希望在替换术语时应用Production 6,并且下一个输入符号是数字或左括号.生产5-另一个右侧 - 以一个术语开始,该术语可以以一个因子开始,该因子可以以数字或左括号开头,这些是用于选择生产6的相同符号.
书中的第二句话让我彻底迷失了.所以通过使用一些语句的例子(例如)5 + (7*4) + 14:
compiler-construction recursion parsing recursive-descent left-recursion
作为练习,我正在使用以下GADT为Haskell中定义的极其简单的语言实现一个解析器(我的项目的真正语法涉及更多表达式,但这个提取对于这个问题已经足够了):
data Expr a where
I :: Int -> Expr Int
Add :: [Expr Int] -> Expr Int
解析函数如下:
expr :: Parser (Expr Int)
expr = foldl1 mplus
[ lit
, add
]
lit :: Parser (Expr Int)
lit = I . read <$> some digit
add :: Parser (Expr Int)
add = do
i0 <- expr
is (== '+')
i1 <- expr
is <- many (is (== '+') *> expr)
pure (Add (i0:i1:is))
由于表达式语法的左递归性质,当我尝试解析像1+1使用expr解析器一样简单的东西时,解析器陷入无限循环.
我已经看到了如何使用以下内容的转换在Web上分解左递归的示例: …
我有一个语法文件,用于我正在尝试构建的新通用编程语言.我正在尝试使语言健壮且自然地使用(它受到Ruby等人的很大启发),并且在这样做时我引入了一些左递归规则.
我看过一些似乎表明以下左递归规则的例子:
rule l_recurse
l_recurse / 'something else'
end
可以通过将其更改为以下来进行非左递归:
rule r_recurse
'something else' / r_recurse
end
对我来说,这似乎会有一个不同的问题,但仍然会失败.我是对的,还是这个"只是工作"？
我正在尝试(查找和)消除的特定左递归在此语法文件中找到.我不确定哪些规则受到影响,但至少有一些规则被指出有左递归.(顺便说一下,我试图通过收紧范围规则来消除他提到的具体范围问题.)
我在这个语法中有一个左递归的小问题.我正在尝试在Prolog中编写它,但我不知道如何删除左递归.
<expression> -> <simple_expression>
<simple_expression> -> <simple_expression> <binary_operator> <simple_expression>
<simple_expression> -> <function>
<function> -> <function> <atom>
<function> -> <atom>
<atom> -> <number> | <variable>
<binary_operator> -> + | - | * | /
expression(Expr) --> simple_expression(SExpr), { Expr = SExpr }.
simple_expression(SExpr) --> simple_expression(SExpr1), binary_operator(Op), simple_expression(SExpr2), { SExpr =.. [Op, SExpr1, SExpr2] }.
simple_expression(SExpr) --> function(Func), { SExpr = Func }.
function(Func) --> function(Func2), atom(At), { Func = [Func2, atom(At)] }.
function(Func) --> atom(At), { Func = At }.
我写过类似的东西,但它根本不起作用.如何更改它以使该程序正常工作？
我正在尝试解析逗号分隔的列表。为了简单起见，我只使用数字。这些表达式是有效的：
(1,4,3)
()
(4)
我可以想到两种方法来做到这一点，我想知道为什么失败的例子不起作用。我相信它是正确的 BNF，但我无法让它像 PEG 一样工作。谁能准确解释为什么吗？我试图更好地理解 PEG 解析逻辑。
我正在使用在线浏览器解析器生成器进行测试： https: //pegjs.org/online
这不起作用：
list = '(' some_digits? ')'
some_digits = digit / ', ' some_digits
digit = [0-9]
（实际上，它解析得很好，喜欢 () 或 (1)，但不识别 (1, 2)
但这确实有效：
list = '(' some_digits? ')'
some_digits = digit another_digit*
another_digit = ', ' digit
digit = [0-9]
这是为什么？（语法新手看这里）
我想制作一个允许curried函数调用的语法.
那是:
a() /// good
a()() /// good
a()()() /// good
a(a) /// good
a(a()()) /// good
/// etc
我的第一个刺是这样的:
ID : ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*;
fncall : expr '(' (expr (',' expr)*)? ')';
expr : ID|fncall;
但由于左递归而失败.