Python Forum
Need help with PEG Grammar
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Need help with PEG Grammar
#1
Hello, I am an undergraduate student who's doing undergrad research on language grammars. My specific task is to convert different language grammars to BNF grammar so that those can be used on Bison. Python grammar till 3.8.x was LL(1) grammar that could be converted to BNF without much effort. But the new PEG and EBNF is a bit confusing for me. I'm having hard time converting & ! etc to BNF. For example, the following rule is changed to BNF by doing some workaround-
Original:
slices:
| slice !','
| ','.slice+ [',']


BNF:
%token COMMA
`
slices:
slice
| slices_seperated_by_comma
| slices_seperated_by_comma COMMA
;
slices_seperated_by_comma:
slice COMMA slice
| slice COMMA slice COMMA slice
| slices_seperated_by_comma slices_seperated_by_comma
;

This was done by keeping in mind that single slice will not have comma at the end. But multiple comma-separated slices might have trailing comma. And more than one comma-separated slice can be either two slices or three slices or a combination of them.

However, this becomes far complicated when there are more than one ! in a rule. And when it's ~, I cannot even think of a way to convert it to BNF.

Is there any algorithm I can follow while converting from PEG to BNF? And if not, what are the approaches that might help me converting? Or is converting the new grammar even possible? If not, then I will go back to 3.8.x grammar.

Hoping to get some good suggestion. Thanks in advanced.
Reply
#2
For Python 3.8's grammar, I wrote a railroad diagram in this thread. You could perhaps try to write similar railroad diagrams for the PEG grammar and this would help converting to BNF.

To find something similar to the «slices» category above, look at the railroad diagram of «testlist_comp» in Python 3.8's grammar. It is very similar to the slices. In view of the railroad diagram, I would have written something like
Output:
slices: slice | slice comma_slice_list | slice comma_slice_list COMMA ; comma_slice_list: COMMA slice | comma_slice_list COMMA slice ;
Reply
#3
(Jun-02-2022, 09:53 PM)Gribouillis Wrote: For Python 3.8's grammar, I wrote a railroad diagram in this thread. You could perhaps try to write similar railroad diagrams for the...

Thanks a lot.
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020