4 ms·
You can use it for braces too, with some relatively simple additional rules. Braces the way they're used in most languages are "just" a special case of parenthe
by vidarh 9y ago
You can use it for braces too, with some relatively simple additional rules. Braces the way they're used in most languages are "just" a special case of parentheses: You need to recurse, and the closing parenthesis/brace needs to trigger reduce all the way to a single value.
If you're willing to sacrifice a bit more generality you can parse a lot more. E.g. my (very much in-progress and incomplete) Ruby compiler uses precedence parsing with tweaks to parse most of the Ruby grammar, including blocks (do/end, {/}), array indices and initializers (foo[1], vs [1,2,3]) and more.
It's been hell to adjust the priorities, and it's not correct yet, but I also think it can be cleaned up quite a bit more. The biggest pain point, actually, is tidying up the generated tree to remove superfluous nodes and flaten various bits, and that's where I'll need to do the most work to simplify.
There are of course ugly parts of this with Ruby that ruined my originally quite nice and clean generic shunting yard code. E.g. if "foo" is a local variable "foo [1]" should parse as "foo.[](1)" (that is '[]' is a method name), while if "foo" is not a local variable, it is implicitly a method call, and "foo [1]" should parse as "foo([1])" with "self" as implicit receiver. I've for now resolved that by having a few "artificial" terminals to handle this and a few other ambiguities that are picked based on context and resolved later, but I'm really not happy about it. Worst case is I "surrender" and convert it to a recursive descent like the higher levels of the grammar, but I want to see what I can do with the current one first.
Currently the full parser, which still lacks some parts of Ruby is about 1600 lines of Ruby (including the lexical tokenizer and some generic parser/scanner utility classes), which I'm distinctly displeased about - it's much smaller than MRI, but not as much smaller as I think should be possible, especially since it's still missing pieces; granted there's a lot of comments, but I think parsing Ruby in Ruby should be doable in <1000 lines of Ruby code using recursive descent + precedence parsing despite Ruby's many idiosyncracies. Less if you exclude the code for a decent generic parser library. I think that says a lot of the simplicity of applying both recursive descent and precedence parsing..
- seanmcdirmid 9y agoNote I was using brace synonymously with paren (to me, parens are just a special kind of brace, I assume you are equating brace with bracket). Sure, you can also deal with terminal overloading using adjacency if you want. However, the parser gets more complex and it becomes less worth it. In the parsers I build, I match braces in a separate earlier phase anyways (you don’t need a parser to do that, and it makes the parser much more robust if you do). However, the main drawback of a precedence parser is that you don’t get any parse errors out of it, and you have to manually go back and check that your trees are actually well formed. So I’ve went back to pure recursive descent.
- vidarh 9y ago> However, the parser gets more complex and it becomes less worth it. It really doesn't change much. Here's a simple one that can handle simple function call syntax: https://gist.github.com/vidarh/a109c3788044736568bd71e79e842f0f https://gist.github.com/vidarh/a109c3788044736568bd71e79e842... Apart from the operator definitions, to handle parentheses it contains two checks for the ":lp" operator type I used for left parentheses / any other tokens like brackets that'd behave the same, and one line to force :rp (right/closing parenthesis) to trigger a reduce. 40-something of those lines are the actual shunting yard/precedence parsing. The variant I use for my Ruby parser does have some extra (ugly) hacks needed to deal with Ruby ambiguities, and "fun" stuff like variable arity operators (e.g. to handle method calls or things like "return") but the above is pretty much what you need to deal with saner grammars in a fairly generic way. > you don’t need a parser to do that, and it makes the parser much more robust if you do That very much depends on the language. In Ruby for example, the meaning of both parenthesis and curly/square brackets is context-sensitive. E.g. {} is a Hash literal. "foo {}" is a method call with a block. Or one of my "favorites": foo(5,1) is valid and has two arguments. foo(5,:bar => :baz) is valid. foo(:bar => :baz,5) is a syntax error ( "=>" is expected rather than ")" as the first "=>" turned it and all following elements of the argument list into an implicit Hash literal (so the last two ones are equivalent to foo(5, {:bar => :baz) and foo({:bar => :baz, 5}) respectively). There are more caveats, but I don't remember all of them off the top of my head. Some of them you could probably handle quite easily while pre-parsing, but you'd need to apply at least some grammar rules as many constructs acts very differently depending on whether or not an operator is used as prefix or infix for example. E.g. "% foo " is the literal quoted string "foo" (space acts as the quote character) while (foo % bar) is foo modulo bar, so you can't even safely tokenize Ruby without some thought to the preceding token at a minimum. > However, the main drawback of a precedence parser is that you don’t get any parse errors out of it, and you have to manually go back and check that your trees are actually well formed. Sure you do. If the value stack contains fewer arguments than the current operator requires after any reduce step that the priorities require, you have an error, and the cause is generally straightforward enough to place. Constructing precise errors from that can be a bit painful, but it usually points at the "correct" spot if you record the locations of tokens, and the priorities lets you process the priorities of the operators and easily enough determine what would be valid. I'm not sure how you'd use it to end up with invalid trees. In the contexts I've used it, the tokenizer combined with the precedence table is enough to ensure that the trees are syntactically well formed. If you want to apply semantic checks, you can just as easily call out to do those tests with a precedence parser as with a recursive descent one.