4 ms·
> 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 s
by 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.
- seanmcdirmid 9y agoBraces sound like they are always balanced in Ruby, so you can match them outside of the parser even if you don’t know how they will be used. You still have to “parse”, but freeing your parser from matching leads to more robust parses. The only place where a pre match step doesn’t work is when you have tokens that are overloaded to sometimes be braces or not; I.e. < and > in most languages after C++ that has generics. Actually, you need non deterministic parsing in most cases with these, which is a pain and I wish new languages wouldn’t keep copying this mistake (typescript). It looks like you are checking correctness in your precedence parser, which is fine, but it’s not possible to do that for many languages.
- vidarh 9y ago> Braces sound like they are always balanced in Ruby, so you can match them outside of the parser even if you don’t know how they will be used. You still have to “parse”, but freeing your parser from matching leads to more robust parses. I don't see what you mean when you say it makes it more robust. They're no different than other operators and punctuation. With respect to balancing, I'm actually not sure, There are sufficient corner cases to try to exploit that it's not obvious to me if you can or can't construct cases that'd be hard to get right. Writing a Ruby parser keeps teaching me corners of the grammar that I've never touched in 13 years of using the grammar... Many of them are dark corners I've never seen in the wild, and hope I never do. With respect to "<>", you certainly can do %<foo> in Ruby, but that's easy enough to handle in the tokenizer, assuming you add a token lookbehind so I don't think it changes things (needed to know if "%" is the modulo operator or starting a quoted string). Meanwhile "%>foo>" means the same ("<[{(" after "%" starts a quoted string that ends with the "closing" sybol, but most other non-alphabetic symbols starts a quoted string that ends with the same symbol - unfortunately this includes whitespace) I'm starting to think you may be right they'll be ok to handle separately, though I still don't see a reason to do it. > It looks like you are checking correctness in your precedence parser, which is fine, but it’s not possible to do that for many languages. Depends what you mean by "checking for correctness". In the simplest form, such as the example I posted, it is applying one very basic check: Does the number of available values on the value stack match what is required by the operator currently being processed? The only thing you need to be able to do in order to do that is to be able to split the tokens into operators and other symbols (which are all values/operands as far as the precedence parser is concerned), and match the operators against a list of operator types and priorities. If you can do that, you can construct a well formed tree as per the rules specified by the precedence parser configuration. If you can't, you probably shouldn't parse it with that parser, but should instead either augment the parser to support what you need, or use something else. It sounds to me as if you're checking the trees afterwards because you've shoehorned a grammar that's beyond the capabilities of the specific precedence parser into using it anyway but deliver trees that matches what you've actually specified but not what you want, and that this is what you don't consider well formed. That's fair enough, and I've done post-processing myself too, but generally I've come to think it's better to push capabilities to build the tree the way you want it in the first place to the parser. In any case I don't really consider that "fixing" malformed trees: The parser will only accept trees that are syntactically valid according to the classification of the tokens and the precedence rules.