4 ms·

This seems similar to grammars described by DTTs (predecessor to XML Schema), in that it's regular expressions, that must be deterministic, that can recurse, bu

This seems similar to grammars described by DTTs (predecessor to XML Schema), in that it's regular expressions, that must be deterministic, that can recurse, but only when isolated by a tag. That is, recursion always results in nested elements, never a sequence of iterated elements: yes: S -> <a> S </a> | e no: S -> <a></a> S | e I've seen these called "tree grammars". Perhaps it's identical with "visibly pushdown grammars"? I skimmed the wiki link (from your readme.md), but it requires further study. I think it would be great if your readme.md included a brief idea, along the lines of what your comment here.

panic 8y ago
I think they're the same thing, though IIRC tree grammars are usually defined to operate on actual trees rather than strings of text.
- hyperpallium 8y ago
  I played around with tree grammars. I think there's a formal language reason for them being incapable of parsing expressions properly. I tried anyway, to find a subset or workaround that would work well enough, but failed. (IIRC) At best, I needed parentheses around one of the operator operations e.g. always around +, like (a+b)c or (a+bc) I'm interested that you have this too, but it seems to have the same problems I found: https://news.ycombinator.com/item?id=17650770 https://news.ycombinator.com/item?id=17650770 It would be very exciting if you have found a way around this!
  - panic 8y ago
    Yeah, this is a fundamental problem. Luckily, arithmetic expressions are always left- or right-recursive, never middle-recursive. That means they're recognizable by a regular grammar, even if the parse tree doesn't match what you'd expect: expr = number (('*' | '+') number)* You can replace number by (number | [ '(' expr ')' ]) to add support for parentheses as well. My solution was to add special syntax which makes rules like this automatically: expr = number : num .operators infix left '*' : times .operators infix left '+' : plus While the parse tree is built, the operators and operands are rearranged into the expected parse tree using https://en.wikipedia.org/wiki/Shunting-yard_algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm. Here's an interactive example with some more operators: https://ianh.github.io/owl/try/#expr https://ianh.github.io/owl/try/#expr
    - hyperpallium 8y ago
      Thanks, the eg I tried before works now, I must have misinterpreted the output. Nice, a language can be recognized, even if a different parse tree. I vaguely recall the shunting yard algorithm... am I right in characterising your solution as a second level of parsing? It's not "pure", but from a practical point of view, it's no worse than back-references in PCRE. The practical issue is just of ui usability.

panic 8y ago

I think they're the same thing, though IIRC tree grammars are usually defined to operate on actual trees rather than strings of text.

hyperpallium 8y ago
I played around with tree grammars. I think there's a formal language reason for them being incapable of parsing expressions properly. I tried anyway, to find a subset or workaround that would work well enough, but failed. (IIRC) At best, I needed parentheses around one of the operator operations e.g. always around +, like (a+b)c or (a+bc) I'm interested that you have this too, but it seems to have the same problems I found: https://news.ycombinator.com/item?id=17650770 https://news.ycombinator.com/item?id=17650770 It would be very exciting if you have found a way around this!
- panic 8y ago
  Yeah, this is a fundamental problem. Luckily, arithmetic expressions are always left- or right-recursive, never middle-recursive. That means they're recognizable by a regular grammar, even if the parse tree doesn't match what you'd expect: expr = number (('*' | '+') number)* You can replace number by (number | [ '(' expr ')' ]) to add support for parentheses as well. My solution was to add special syntax which makes rules like this automatically: expr = number : num .operators infix left '*' : times .operators infix left '+' : plus While the parse tree is built, the operators and operands are rearranged into the expected parse tree using https://en.wikipedia.org/wiki/Shunting-yard_algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm. Here's an interactive example with some more operators: https://ianh.github.io/owl/try/#expr https://ianh.github.io/owl/try/#expr
  - hyperpallium 8y ago
    Thanks, the eg I tried before works now, I must have misinterpreted the output. Nice, a language can be recognized, even if a different parse tree. I vaguely recall the shunting yard algorithm... am I right in characterising your solution as a second level of parsing? It's not "pure", but from a practical point of view, it's no worse than back-references in PCRE. The practical issue is just of ui usability.