4 ms·
Recursive descent parsers have trouble with left-associative operators if you only allow recursion. But if you allow iteration, you can build up the parse tree
by tlb 4y ago
Recursive descent parsers have trouble with left-associative operators if you only allow recursion. But if you allow iteration, you can build up the parse tree while iterating through terms at the same precedence level. For example, this defines + and - as left-associative at the same precedence level:
// EBNF is SUM = PRODUCT , { ("+" | "-") , PRODUCT }
AstNode *parseSum()
{
if (auto lhs = parseProduct()) {
while (1) {
if (consume(T_PLUS)) {
if (auto rhs = parseProduct()) { // You'd call parseSum instead to get right associativity
lhs = mkAst(A_add, lhs, rhs); // Instead, left associativity happens here
}
else {
return nullptr;
}
}
else if (consume(T_MINUS)) {
if (auto rhs = parseProduct()) {
lhs = mkAst(A_sub, lhs, rhs);
}
else {
return nullptr;
}
}
else {
return lhs;
}
}
}
else {
return nullptr;
}
}
As a bonus, it doesn't blow out your stack when parsing long expressions.
Very few binary operators should be right-associative. Basically just ?: and = .
- ufo 4y agoThe price for this is that you have to refactor the grammar, replacing all uses of left recursion with right recursion (iteration).
- bear8642 4y agoWhich might then change the semantics of your grammar - remember this being pointed out in 3rd year compilers course
- peterfirefly 4y agoSeems like a relevant place to put a link to this paper: David R. Hanson, "Compact Recursive-descent Parsing of Expressions", 1985 https://drhanson.s3.amazonaws.com/storage/documents/compact.pdf https://drhanson.s3.amazonaws.com/storage/documents/compact.... There are languages (such as ML) that allow the definition of new operators with a choice of precedence and associativity. Using a table like the one Hanson suggests and modifying it at compile-time is an obvious way to handle that feature.
- bruce343434 4y agoWhen you do precedence like this in recdesc, you will get functions like parse_prec_1, parse_prec_2 and so forth. If you generalize this function body, and pass along a "current precedence", then generalize the precedences for each operator into a table, you have just reinvented Pratt Parsing.