How to implement Backus-Naur Form in Python

python parsing grammar bnf
Jakemmarsh picture Jakemmarsh · Dec 23, 2012 · Viewed 19k times · Source

I know there are some vaguely similar questions already relating to BNF (Backus-Naur Form) grammars in Python, but none of them help me much in terms of my application.

I have multiple BNFs that I need to write code for. The code should be able to both generate and recognize legal strings using the BNF grammar.

The first BNF I'm working with is for all real numbers in Python. It is as follows:

<real number>    ::= <sign><natural number> |
                     <sign><natural number>'.'<digit sequence> |
                     <sign>'.'<digit><digit sequence> |
                     <sign><real number>'e'<natural number>
<sign>           ::= ‘’ | ‘+’ | ‘-‘
<natural number> ::= ‘0’ | <nonzero digit><digit sequence>
<nonzero digit>  ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<digit sequence> ::= ‘’ | <digit><digit sequence>
<digit>          ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Any BNF parsers I've found for Python seem extraordinarily complex, or use outside libraries. Is there any simpler way to check against and generate using BNF grammar in Python?

Answer

Vinay Sajip picture Vinay Sajip · Dec 23, 2012

This post contains an example of a lexical scanner which doesn't need third-party libraries. It may not do all you want, but you should be able to use it as a basis for something that fits your needs.

I don't know if your applications all relate to lexical scanning - but if not, ply is a fairly easy to use parser (given that you need to know broadly how parsers work).

Edit: A backup of the cited page is on archive.org:

Related questions

Efficient Context-Free Grammar parser, preferably Python-friendly

I am in need of parsing a small subset of English for one of my project, described as a context-free grammar with (1-level) feature structures (example) and I need to do it efficiently . Right now I'm using NLTK's parser which …

Read More
How do I get a set of grammar rules from Penn Treebank using python & NLTK?

I'm fairly new to NLTK and Python. I've been creating sentence parses using the toy grammars given in the examples but I would like to know if it's possible to use a grammar learned from a portion of the Penn …

Read More
How do I parse a string to a float or int?

In Python, how can I parse a numeric string like "545.2222" to its corresponding float value, 545.2222? Or parse the string "31" to an integer, 31? I just want to know how to parse a float str to a float, and (separately) an int …

Read More