Text parsing, formal grammars and BNF introduction

20 Jan 2008  Development, Various

Exercise 1: try to define a BNF definition for a greeting: “Hello, John!”, where ‘John’ can be any name starting with an uppercase character, followed by some lowercase ones.

Answer:

  • lccharacter ::= a | b | c | d | e | f | … | z
  • uccharacter ::= A | B | C | D | F | … | Z
  • lcseq ::= lccharacter | lccharacter lcseq
  • name ::= uccharacter lcseq
  • greeting ::= “Hello, ” name “!”

Obviously, you could have chosen other names. Notice the “” in the greeting definition. This stresses the fact these constant words are not part of the metalanguage.

Exercise 2: write a BNF definition for a standard printf-style function, which accepts string (”%s”) and integer (”%d”) values. The formatting string can consist of any alphanumeric character, spaces and formatters. Variable names can consist of any alphanumeric character, but can’t start with a number.

Answer:

  • charseq ::= lcchar | ucchar | lcchar charseq | ucchar charseq
  • varname ::= charseq | charseq digits | charseq digits varname
  • formatter ::= “%d” | “%s”
  • word ::= lcchar | ucchar | digit | lcchar word | ucchar word | digit word
  • part ::= formatter | word | ” “
  • spaced ::= part | ” ” part | part ” ” | ” ” part ” “
  • arg ::= spaced | spaced spaced
  • varlist ::= varname | varname “, ” varname | varname “, ” varlist
  • optarglist ::= “” | “, ” varlist
  • printf ::= “printf(” arg optarglist “);”

This one might look somewhat big, and maybe the rule names weren’t that well-chosen, sorry about that, but you should be able to recognize some parts.
Disclaimer: I just wrote down these by hand, there might be some mistakes in them.

Pages: 1 2

Tags: , , ,

Related entries

12 Responses to “Text parsing, formal grammars and BNF introduction”

  1. Anonymous said on 20 Jan 2008 @ 5:27 am

    Shouldn’t that be: integer ::= digit | nzdigit digits ? Otherwise, your language could not parse “0″.

  2. fok said on 20 Jan 2008 @ 6:40 am

    there are several parsing modules for python beyond pyparsing. My personal preference is ply (http://www.dabeaz.com/ply/)

  3. RubenV said on 20 Jan 2008 @ 12:50 pm

    Interesting, but I think the issue of ambiguous grammars is missing. These bring their own class of problems.

    Also, it might be interesting to mention the fact that regular expressions simply cannot represent the same class of languages as grammars. This is the very reason one would like to use grammars, which are inherently harder to parse (you need a PDA whereas a regular expression can be processed using a finite state automaton). On the other hand, the inexpressivity of regular expressions is the reason why they are used that often, they can be implemented very efficiently. You see, there is no free lunch :-)

    I can highly recommend Michael Sipser’s book on this topic: Introduction to the Theory of Computation. It’s a bit tough, but highly comprehensive (and very well written). More here: http://www-math.mit.edu/~sipser/book.html

  4. Nicolas said on 20 Jan 2008 @ 1:41 pm

    Anonymous: correct! Fixed, thanks.

    Fok: I kinda dislike the non-Pythoness of Yakk, and as a result the kinda hard to understand syntax of PLY. Thanks for the pointer though :-)

    Ruben: can’t any BNF definition be translated into a set of regular expressions and controller code?

  5. Mattias Bengtsson said on 20 Jan 2008 @ 3:32 pm

    I’ve been using BNFC (BNF Converter) for some compiler construction courses at school. I think it is a really neat project. It can generate Java, Haskell and C++-parsers. I’m not sure if it can output Python parsers though.

  6. no one in particular said on 20 Jan 2008 @ 6:46 pm

    For the record, note that you’ve described the whole numbers, not the integers, because integers include negative numbers.

    (I’m not trying to be annoying, but I figured it was worth pointing out. Thanks for the interesting read!)

  7. RubenV said on 20 Jan 2008 @ 6:46 pm

    Nicolas: Try expressing a language which recognizes balanced brackets, which can be arbitrarily nested using a regular expression.

    Fairly trivial in BNF, impossible to implement using traditional regular expressions.

  8. Nicolas said on 20 Jan 2008 @ 7:30 pm

    no one in particular: indeed… I translated it somewhat badly. So to be correct:

    • whole_number ::= digit | nzdigit digits
    • sign ::= “-” | “+” | “”
    • integer ::= sign whole_number

    Ruben: out of my head, if input is ‘foo(bar(baz)bat)’, can’t you do something like

    parts = []
regex = '^([.^(]*)[\(([.^)]*)\)]*(.*)$'

def parse(s):
    parts = regex.parse(s)
    parts.append(parts[0])
    for i in range(1, len(parts)):
        parse(parts[i])

parse(s)
  9. RubenV said on 20 Jan 2008 @ 8:52 pm

    Nicolas: You’re cheating there by combining recursion and regular expressions :-). Pure regular expressions can’t do that. Recursion is actually what sets regular languages and context free grammars apart.

  10. ethana2 said on 21 Jan 2008 @ 9:45 am

    Lojban would have been perfect if it had a proper phonetic base.
    After I fork it and make the Best Language on Earth, we can avoid this nonsense ;)

  11. sar said on 23 May 2008 @ 6:52 pm

    Hi,

    I’am a student , and as a project I have to write a grammar (LBNF one) -and it’s ok for it-; then, I have to use the BNFC, and that’s th e pb i.e. Idon’t know how to use it.

    Please help me. and thanks a lot.

    Best regards.

  12. arrok said on 20 Oct 2008 @ 4:59 am

    idea armistice trusted. favourable hold upon someone word advice Acquisto Viagra on numerous occasions that percipience.

Leave a comment