Debugging yecc grammars: what techniques are available?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Debugging yecc grammars: what techniques are available?

Hugo Mills-2
   I'm in the process of writing a domain-specific language, using a
custom lexer and a yecc parser. In the process of attempting to add a
new feature to the grammar, I've managed to break what appears to me
to be a completely unrelated piece of the grammar: I'm adding a
structure similar to a list comprehension, and suddenly the integer
comparison operators have stopped working in one group of cases.

   What approaches are there for debugging this kind of problem? The
best I can some up with is inspection of the .yrl source in detail,
but that's not helping. How else can I work out what the issue is?

   Obviously, I could post the grammar here for inspection by more
experienced minds than mine, but I'd prefer to find better tooling and
techniques rather than mere appeal to higher authority...

   Hugo.

--
Hugo Mills             | Strive for apathy!
hugo@... carfax.org.uk |
http://carfax.org.uk/  |
PGP: E2AB1DE4          |                                      Andrew Zalotocky

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Debugging yecc grammars: what techniques are available?

Walter Weinmann
I've done a project with he OpenCypher language: https://github.com/walter-weinmann/ocparsehttps://github.com/walter-weinmann/ocparse. This should be a good example how to apply leex and yecc.

I've done also a second one, but honestly I'm very unhappy with the limitations of LALR parsing. I'm now in the process to switch to neotoma, which is based on Parser Expression Grammars and it looks very promising.

Regards

Walter


On 5 February 2017 at 00:45, Hugo Mills <[hidden email]> wrote:
   I'm in the process of writing a domain-specific language, using a
custom lexer and a yecc parser. In the process of attempting to add a
new feature to the grammar, I've managed to break what appears to me
to be a completely unrelated piece of the grammar: I'm adding a
structure similar to a list comprehension, and suddenly the integer
comparison operators have stopped working in one group of cases.

   What approaches are there for debugging this kind of problem? The
best I can some up with is inspection of the .yrl source in detail,
but that's not helping. How else can I work out what the issue is?

   Obviously, I could post the grammar here for inspection by more
experienced minds than mine, but I'd prefer to find better tooling and
techniques rather than mere appeal to higher authority...

   Hugo.

--
Hugo Mills             | Strive for apathy!
hugo@... carfax.org.uk |
http://carfax.org.uk/  |
PGP: E2AB1DE4          |                                      Andrew Zalotocky

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions





_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Debugging yecc grammars: what techniques are available?

Mikael Pettersson-5
In reply to this post by Hugo Mills-2
Hugo Mills writes:
 >    I'm in the process of writing a domain-specific language, using a
 > custom lexer and a yecc parser. In the process of attempting to add a
 > new feature to the grammar, I've managed to break what appears to me
 > to be a completely unrelated piece of the grammar: I'm adding a
 > structure similar to a list comprehension, and suddenly the integer
 > comparison operators have stopped working in one group of cases.
 >
 >    What approaches are there for debugging this kind of problem? The
 > best I can some up with is inspection of the .yrl source in detail,
 > but that's not helping. How else can I work out what the issue is?
 >
 >    Obviously, I could post the grammar here for inspection by more
 > experienced minds than mine, but I'd prefer to find better tooling and
 > techniques rather than mere appeal to higher authority...

Caveat: while I have experience with various parsing techniques, including
LALR(1), I have none with the yecc tool.

Does yecc issue any warnings about shift/reduce or reduce/reduce conflicts?
If it does, you need to investigate those and resolve them.  With yacc and
bison it's possible to manually inspect the LALR(1) automaton for debugging.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Debugging yecc grammars: what techniques are available?

Richard Carlsson-3
In reply to this post by Walter Weinmann
It can be pretty tricky to figure out what's wrong with a grammar, in particular if the parser generator doesn't have support for emitting various kinds of debug information. Here are some links that might help you:

You might want to consider porting the grammar to Bison (which has better debugging support) and use that instead for the development/debugging phase, then port it back to yecc for the final implementation when done.



        /Richard

2017-02-05 7:49 GMT+01:00 Walter Weinmann <[hidden email]>:
I've done a project with he OpenCypher language: https://github.com/walter-weinmann/ocparsehttps://github.com/walter-weinmann/ocparse. This should be a good example how to apply leex and yecc.

I've done also a second one, but honestly I'm very unhappy with the limitations of LALR parsing. I'm now in the process to switch to neotoma, which is based on Parser Expression Grammars and it looks very promising.

Regards

Walter


On 5 February 2017 at 00:45, Hugo Mills <[hidden email]> wrote:
   I'm in the process of writing a domain-specific language, using a
custom lexer and a yecc parser. In the process of attempting to add a
new feature to the grammar, I've managed to break what appears to me
to be a completely unrelated piece of the grammar: I'm adding a
structure similar to a list comprehension, and suddenly the integer
comparison operators have stopped working in one group of cases.

   What approaches are there for debugging this kind of problem? The
best I can some up with is inspection of the .yrl source in detail,
but that's not helping. How else can I work out what the issue is?

   Obviously, I could post the grammar here for inspection by more
experienced minds than mine, but I'd prefer to find better tooling and
techniques rather than mere appeal to higher authority...

   Hugo.

--
Hugo Mills             | Strive for apathy!
hugo@... carfax.org.uk |
http://carfax.org.uk/  |
PGP: E2AB1DE4          |                                      Andrew Zalotocky

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions





_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Debugging yecc grammars: what techniques are available?

Hugo Mills-2
In reply to this post by Mikael Pettersson-5
   Thanks to all who replied on this thread, and apologies for not
getting back sooner -- more urgent things got in the way.

On Sun, Feb 05, 2017 at 11:18:39AM +0100, Mikael Pettersson wrote:

> Hugo Mills writes:
>  >    I'm in the process of writing a domain-specific language, using a
>  > custom lexer and a yecc parser. In the process of attempting to add a
>  > new feature to the grammar, I've managed to break what appears to me
>  > to be a completely unrelated piece of the grammar: I'm adding a
>  > structure similar to a list comprehension, and suddenly the integer
>  > comparison operators have stopped working in one group of cases.
>  >
>  >    What approaches are there for debugging this kind of problem? The
>  > best I can some up with is inspection of the .yrl source in detail,
>  > but that's not helping. How else can I work out what the issue is?
>  >
>  >    Obviously, I could post the grammar here for inspection by more
>  > experienced minds than mine, but I'd prefer to find better tooling and
>  > techniques rather than mere appeal to higher authority...
>
> Caveat: while I have experience with various parsing techniques, including
> LALR(1), I have none with the yecc tool.
>
> Does yecc issue any warnings about shift/reduce or reduce/reduce conflicts?
> If it does, you need to investigate those and resolve them.  With yacc and
> bison it's possible to manually inspect the LALR(1) automaton for debugging.
   This turned out to be my main problem: I actually had 20 unresolved
shift/reduce conflicts, but in the yecc output, they were listed at
the top of a giant list of properly resolved conflicts (using
precedence rules), and I hadn't seen them.

   I fixed up those problems, and several more that arose elsewhere in
the grammar once those had been removed (for example, duplicate
definitions of some structures like comma-separated lists). This fixed
up a bunch of my parser test failures. Then I found that the
problematic integer comparison operators had actually been only
coincidentally passing the unit tests, and that the test failures I
was seeing were correct -- so I fixed a bug in the evaluator code for
those.

   Finally, I worked out how to give function invocation a high
precedence, which has, I think, fixed the last remaining issue I had
with the grammar. (I can now write f(3)(6) and 3+g(3) and get the
correct parse trees).

   I've still got some known bugs in the evaluator, but they're not
parser problems, and I know how to fix those easily enough.

   Thanks,
   Hugo.

--
Hugo Mills             | "There's more than one way to do it" is not a
hugo@... carfax.org.uk | commandment. It is a dire warning.
http://carfax.org.uk/  |
PGP: E2AB1DE4          |

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

signature.asc (853 bytes) Download Attachment