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

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

[Luke Kenneth Casson Leighton]

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

here's how python-ply is supposed to work:
http://www.dabeaz.com/ply/ply.html#ply_nn27

here's a patch showing the relevant files involved:
https://git.libre-riscv.org/?p=soc.git;a=commitdiff;h=39c8314f9a14fb5351a9dcbc8bd37753bdcd0fee

executing "python3 soc/decoder/power_pseudo.py" is a good test, with
this being good example code:
+cmpi = """
+in_range <-  (x | y) & (a | b)
+in_range <-  (x + y) - (a + b)
+"""

help appreciated.

l.

_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

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

[Jacob Lifshay]

On Fri, Apr 3, 2020, 08:20 Luke Kenneth Casson Leighton <lkcl@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

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).

>
> here's how python-ply is supposed to work:
> http://www.dabeaz.com/ply/ply.html#ply_nn27
>
> here's a patch showing the relevant files involved:
>
> https://git.libre-riscv.org/?p=soc.git;a=commitdiff;h=39c8314f9a14fb5351a9dcbc8bd37753bdcd0fee
>
> executing "python3 soc/decoder/power_pseudo.py" is a good test, with
> this being good example code:
> +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. Traditionally + and -
have the same precedence whereas & has higher precedence than | so a & b |
c parses as (a & b) | c.


> help appreciated.
>

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

Jacob
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

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

[Luke Kenneth Casson Leighton]

On Fri, Apr 3, 2020 at 7:23 PM Jacob Lifshay <programmerjake@gmail.com> wrote:
>
> On Fri, Apr 3, 2020, 08:20 Luke Kenneth Casson Leighton <lkcl@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.

l.

_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

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

[Jacob Lifshay]

On Fri, Apr 3, 2020 at 11:50 AM Luke Kenneth Casson Leighton
<lkcl@lkcl.net> wrote:
>
> On Fri, Apr 3, 2020 at 7:23 PM Jacob Lifshay <programmerjake@gmail.com> wrote:
> >
> > On Fri, Apr 3, 2020, 08:20 Luke Kenneth Casson Leighton <lkcl@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.

Just because something has a feature, doesn't mean that it's the best
way to do it.

As far as I can tell, it's working now.

Jacob

_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

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

[Hendrik Boom]

On Fri, Apr 03, 2020 at 11:22:56AM -0700, Jacob Lifshay wrote:
> On Fri, Apr 3, 2020, 08:20 Luke Kenneth Casson Leighton <lkcl@lkcl.net>
> wrote:
...
> > +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. Traditionally + and -
> have the same precedence whereas & has higher precedence than | so a & b |
> c parses as (a & b) | c.

Presumably because the early logicians treated 'and' as being a multiplication
and 'or' as being an addition.

-- hendrik

_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

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

[Luke Kenneth Casson Leighton]

On Fri, Apr 3, 2020 at 9:08 PM Jacob Lifshay <programmerjake@gmail.com> wrote:
> > ply has something called "precedence" which is a list-of-tuples that
> > helps resolve parser ambiguities.
>
> Just because something has a feature, doesn't mean that it's the best
> way to do it.

yeh i know :)  ply was replaced by sly for good reasons.  ply was - is
- FAST.  it did not - does not - use classes because classes use up a
lot more memory and are slower.  however with pretty much everyone now
possessing portable supercomputers, that's no longer so relevant.

the only reason i'm using it is because it's something i've worked
with about... five to eight times now.  i forget :)

> As far as I can tell, it's working now.

fantastic.  thank you.  whew.

l.

_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev