2
$\begingroup$

I am struggle with implementing rules for a custom DSL with significant spaces.

The key feature is that it requires spaces to be tracked and re-used. In most languages they are used to split tokens only, but it is not the case for me, as I want to keep them for specific rules, and discard for others.

Some tests I want to pass:

  • Hello=Bar\n -> Hello + = + Bar + \n
  • Hello world=Bar -> Hello world + = + Bar + \n: before equals there are no two separate tokens, but a sigle one with a whitespace inside.
  • Hello world=Bar -> Hello world + = + Bar + \n: same as above, but two spaces there
  • Hello = Bar -> Hello + = + Bar + \n: all whitespaces between equals are trimmed

So here are some portion of my rules, which I am almost certain of:

definition  : name optional_ws EQUALS optional_ws value NL

value       : SYMBOL  # it is much more complex actually, but I keep it simple for this primer

optional_ws :
            | WS

... and for name I have a rule which DOES what I want, but the definition violated SRP (a SOLID principle), and makes introducing new terminals hard and non-flexible.

name : SYMBOL
     | DIVIDER
     | name SYMBOL
     | name DIVIDER
     | name WS SYMBOL
     | name WS DIVIDER

So that if add a terminal, I would have to add 3 options for the rule, which is awkward.

I tried something like that, but got parsing error.

name       : name_chunk
           | name name_chunk
           | name WS name_chunk

name_chunk : SYMBOL
           | DIVIDER

The test was: foo =bar

I assume it was all about (at least this is how I understood the state machine produces by by yacc tool) that parser consumed WS, put it on stack, attempted the next token of =. Found no resolution for it, since there is nothing satisfying in the name_chunk. My idea was that after this failed attempt WS should return from the stack back to the token queue, and the parser will end with the name, but looks it is not like that at all. But still looking ahead for two terminals (see the "bloated version" of the name) works as I expect.

My terminals are defined with regexes:

NL = \n
WS = \s+
DIVIDER = /
EQUALS = =
SYMBOL = [^\s/=]+

Key notes here:

  • DIVIDER and EQUALS are special tokens which have no meaning in context of a name, so I want to keep then. But they DO however in other contexts, but this is out of the scope of this question, that's whe they have their own terminals.

The final question is: what is the proper way to define a rule for name to pass the tests, so that it would be flexible and error-prone when extending the language and adding new teminals (which should end up in the name as well).

UPDATE. I slightly modified the approach, so that I consume optional whitespace after the name with the name rule rather than by "definition" itself. I ended up with the following grammar (unrelevant rules ommitted):

definition : name EQUALS optional_WS value NEWLINE

name       : name WHITESPACE optional_name_chunk
           | name name_chunk
           | name_chunk

name_chunk : SYMBOL
           | DIVIDER

optional_name_chunk :
                    | name_chunk

In the rule processor (actual parser) of the name rule I just discard optional white space if it has nothing followed with. And this is just exact solution, which passes all my tests, but...

It gives me shift/reduce conflicts. Those are resolved by shift, which is the desired behaviour. So I'd love to hint the parser builder, that I am ok with shift.

I also switched to SLY (improved version of PLY), and used some tooling mentioned in issues there. And I got my conflict visualized.

shift/reduce conflict for DIVIDER in state 8 resolved as shift
   shift using rule name_chunk -> . DIVIDER
   ╭╴
   │ name WHITESPACE ♦ DIVIDER
   │                 ╰name_chunk╯
   │                 ╰optional_name_chunk╯
   │ ╰name──────────────────────────────────╯
   ╰╴

   reduce using rule empty -> .
   ╭╴
   │ name WHITESPACE ♦                     DIVIDER
   │                 ╰empty╯               ╰name_chunk╯
   │                 ╰optional_name_chunk╯
   │ ╰name──────────────────────────────────╯
   │ ╰name──────────────────────────────────────────────────╯
   ╰╴

Obviously, shift is the right solution here. If using reduce path, we would end up in parse error later.

So how do I hint that consuming the DIVIDER and building a chunk from it is the right choice rather that attempting to reduce and build an empty right after the whitespace?

I tried to hint with %prec, but totally no luck here. Probably I am marking the wrong things.

$\endgroup$
4
  • $\begingroup$ Welcome to PLDI! What parser generator are you using? $\endgroup$
    – rydwolf
    Commented Dec 25, 2023 at 20:11
  • $\begingroup$ Hello. I am using PLY. $\endgroup$
    – defance
    Commented Dec 26, 2023 at 7:41
  • $\begingroup$ @RydwolfPrograms please, se question update. I got some movement forward in my struggles. $\endgroup$
    – defance
    Commented Dec 26, 2023 at 10:40
  • 2
    $\begingroup$ Without a reproducible example, it's going to be hard to answer this question. I do think interior whitespace is generally something that should be solved before tokenisation -- like how literal strings are generally parsed as a single token, even if there is whitespace inside. $\endgroup$
    – Jasmijn
    Commented Jan 6 at 10:03

0

You must log in to answer this question.

Browse other questions tagged .