4 ms·

Interesting approach. Maybe it is even better to first start with a back-tracking parser. Although back-tracking has the reputation of being slow, there is a ra

Interesting approach. Maybe it is even better to first start with a back-tracking parser. Although back-tracking has the reputation of being slow, there is a rather straightforward mapping from grammar to functions. Although it is slower than traditional parsing techniques, it is fast enough for many practical applications. One easy trick to optimize back-tracking is memoization. Another is the left-recursion into right-recursion trick, which is also rather straightforward to apply. These two tricks are used in IParse Studio [0] which is an interpreting parser that parses a grammar and uses that grammar to parse some input. I also can help you with rewriting the grammar using the described approach. [0] https://fransfaase.github.io/MCH2022ParserWorkshop/IParseStudio.html https://fransfaase.github.io/MCH2022ParserWorkshop/IParseStu...

Joker_vD 4y ago
What are some of the practical examples that require back-tracking (for whatever definition of "require")? The example I was once being told about was parsing assignment expressions: Expr ::= CanBeLhsOfAssignExpr | CanBeLhsOfAssignExpr "=" Expr | CanNotBeLhsOfAssignExpr but in practice, it's easily parsed in the following manner: def parse_Expr(self): # parse_ExprInner parses CanBeLhsOfAssignExpr or CanNotBeLhsOfAssignExpr cases result = self.parse_ExprInner() if self.peekToken() == TOKEN_ASSIGN: if result.is_CanBeLhsOfAssignExpr: token = self.skipToken() # assignment is right-associative rhs = self.parse_Expr() result = self.make_AssignExpr(token, result, rhs) else: self.raiseParseError("{} can't be target of assignment", result) return result The idea is to parse the prefix under "relaxed" rules, delaying the well-formedness check until it's actually needed.
- fjfaase 4y ago
  I do not know of a simple example, but I have heard there are some example in the C++ grammar where the look-a-head can be as large as possible. Parsers for C(C++) are often not purely grammatical, but also keep a symbol table to resolve these problems. For example, the statement 'a * b;' can either be type definition or a multiplication (with no result) depending on whether 'a' is a type or a variable. Note that in C++ it is possible to defined an *-operator with a side effect.

Joker_vD 4y ago

What are some of the practical examples that require back-tracking (for whatever definition of "require")? The example I was once being told about was parsing assignment expressions: Expr ::= CanBeLhsOfAssignExpr | CanBeLhsOfAssignExpr "=" Expr | CanNotBeLhsOfAssignExpr but in practice, it's easily parsed in the following manner: def parse_Expr(self): # parse_ExprInner parses CanBeLhsOfAssignExpr or CanNotBeLhsOfAssignExpr cases result = self.parse_ExprInner() if self.peekToken() == TOKEN_ASSIGN: if result.is_CanBeLhsOfAssignExpr: token = self.skipToken() # assignment is right-associative rhs = self.parse_Expr() result = self.make_AssignExpr(token, result, rhs) else: self.raiseParseError("{} can't be target of assignment", result) return result The idea is to parse the prefix under "relaxed" rules, delaying the well-formedness check until it's actually needed.

fjfaase 4y ago
I do not know of a simple example, but I have heard there are some example in the C++ grammar where the look-a-head can be as large as possible. Parsers for C(C++) are often not purely grammatical, but also keep a symbol table to resolve these problems. For example, the statement 'a * b;' can either be type definition or a multiplication (with no result) depending on whether 'a' is a type or a variable. Note that in C++ it is possible to defined an *-operator with a side effect.