[libre-riscv-dev] parser precedence, code review / checking needed

Luke Kenneth Casson Leighton lkcl at lkcl.net
Fri Apr 3 19:49:53 BST 2020

On Fri, Apr 3, 2020 at 7:23 PM Jacob Lifshay <programmerjake at gmail.com> wrote:
> On Fri, Apr 3, 2020, 08:20 Luke Kenneth Casson Leighton <lkcl at lkcl.net>
> wrote:
> > if anyone knows how to resolve operator precedence, my logic-dyslexia
> > is kicking in and i am having difficulty working out which operators
> > are supposed to be in which order, for bit-wise AND, OR, and
> > PLUS/MINUS, MUL/DIV.  someone else did the PLUS/MINUS MUL/DIV, i'm
> > attempting to add AND and OR and am getting it wrong
> >
> The way I always did it is by changing the grammar to have one non-terminal
> symbol per precedence level. Example code from my LR(1) parser generator:
> https://github.com/programmerjake/parser-generator/blob/master/test.parser#L108-L120

ply has something called "precedence" which is a list-of-tuples that
helps resolve parser ambiguities.

> If I were writing the parser I would have used either a hand-written
> recursive descent parser (what I used for the shader-compiler-ir text
> parser) or a PEG parser, since PEGs don't have ambiguity since they are
> defined in terms of the steps taken when parsing instead of being defined
> in terms of what strings the rules can produce (LL(1) and LR(1) parsers).

time.  i've used ply before and we're on the clock.  i was able to
(eventually) find GardenSnake.py which had been abandoned somewhere
around 2006, and got it operational in under 2 hours.

that saved potentially weeks of time over writing a from-scratch parser.

> > +cmpi = """
> > +in_range <-  (x | y) & (a | b)
> > +in_range <-  (x + y) - (a + b)
> > +"""
> >
> since there are parenthesis, precedence between &, |, +, and - doesn't
> actually matter here, so it's not a good example.

i'd added them as a way to double-check what the output is (and how it
changes if you do (x&y) | (a&b) rather than as it is at the moment.

astor (btw we need to find a much smaller dependency that can do
tree-dump and to_python_source()) is "smart" - unfortunately - and
only prints out *necessary* brackets.

this is confusing me :)

> Traditionally + and -
> have the same precedence whereas & has higher precedence than | so a & b |
> c parses as (a & b) | c.

i think that's what ("left", BINADD, BINOR) would do.  i'm just not sure.

> Sure, I can figure it out for you if you like. Will be a few minutes.

thanks jacob.


More information about the libre-riscv-dev mailing list