Python grammar: EBNF to Flex & Bison

[narke]

Hello,

I'm trying to write a python interpreter with Flex & Bison.
There is the python grammar available here: http://docs.python.org/dev/py3k/reference/grammar.html.

I take as an example the following specification in EBNF notation from the python grammar:

Code: Select all

file_input: (NEWLINE | stmt)* ENDMARKER

How can I translate this in Flex & Bison?

In a bison file I wrote:

Code: Select all

file_input:
    NEWLINE
  | stmt
  | ENDMARKER
  ;

But this is not pretty exact, as the ENDMARKER is mandatory at the end and here I can't force it.

Do you know how to translate EBNF notation to Flex & Bison?

Thanks in advance!

[Solar]

I have absolutely zero experience with writing for Flex & Bison, but I've read one or two standards documents, so I dare a guess. Would this work?

Code: Select all

# file_input is file_input_statements plus ENDMARKER
file_input:
    file_input_statements ENDMARKER

# file_input_statements (plural) is one or more file_input_statement (singular)
file_input_statements:
    file_input_statement | file_input_statements

# file_input_statement is a statement or a newline
file_input_statement:
    statement | NEWLINE

Syntax is probably off, and naming isn't really intuitive, but I hope I got the idea across. (Credits to ISO 9899:1999...)

[stephenj]

This isn't the best way to do this, but I'm in a hurry to go to work.

Code: Select all

file_input
   : NEWLINE file_input
   | stmt file_input
   | ENDMARKER
   ;

I know books on compilers suck, but you may want to pick one up.

[narke]

As I understand I must find solutions case by case.
This would be a little more difficult than I imaganed but I will try.

[JamesM]

stephenj's solution brings everything into one nonterminal, but the most "honest" translation would probably be

Code: Select all

file_input: file_input_optional ENDMARKER
          ;

file_input_optional: /* Intentionally left blank, for lambda-transition */
                   | NEWLINE file_input_optional
                   | stmt file_input_optional
                   ;

Introducing another nonterminal for the optional Kleene-starred part.