8

Background info (May Skip): I am working on a task we have been set at uni in which we have to design a grammar for a DSL we have been provided with. The grammar must be in BNF or EBNF. As well as other thing we are being evaluated on the Lexical rules in the grammar and the Parsing rules - such as if rules are suitable for the language subset, how comprehensive these rules are, how clear the rules are ect.

What I don't understand is if these rules are covered in a grammar defined in BNF (it's a new topic for us).

The Question: Does a grammar for a given language that has been defined in either BNF or EBNF contain / provide rules for Lexical Analysis and/or Parsing? (or do these have to be specified else-where?)

Also what would be considered a lexical rule? And what would be considered a parsing rule?

The_Neo
  • 191
  • 7
  • 1
    [BNF](http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form) is just a syntax fully describing the grammar just like regex fully describes a regular language – ratchet freak Jan 07 '14 at 17:41
  • 4
    Yes, you can define both lexing and parsing in a single BNF-like description - see PEGs, for example. Distinction between lexing and parsing is pretty arbitrary and outdated. – SK-logic Jan 07 '14 at 17:41

3 Answers3

8

Yes, a BNF grammar contains all the rules you need for lexical analysis and parsing. The difference between the two is a little fuzzy. A good example of a lexical rule in EBNF would be:

number = [ "-" ], digit, { digit } ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

Usually lexers can be implemented using relatively simple code. You can search a string for the next space, then see if your result starts with an optional "-", contains at least one digit after that, and contains only digits after that. Lexers used to almost always be a separate step, but are usually lumped together with the parser nowadays. Hence the fuzziness.

A parser rule would use the number non-terminal to make something larger, like the following addition expression.

add = number, "+", number

Even though they are mixed up in the same file, your professor is still going to want to see a clear distinction between "lexer" rules and "parser" rules. For example, don't do this:

add = {"0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" }, "+",
      {"0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" }

Not only is that error prone, it's difficult to read and difficult to implement.

Karl Bielefeldt
  • 146,727
  • 38
  • 279
  • 479
  • Thanks , the section on making a clear distinction between "lexer" rules and "parser" rules really helped me understand what we're being evaluated for! – The_Neo Jan 07 '14 at 19:49
3

The grammar for lexical analysis is typically specified via regular expressions (especially for university-type projects). It accepts a regular language.

A parser usually accepts a context-free language, which may be specified via BNF.

The distinction between a parser and a scanner (or lexical analyzer) is somewhat artificial, but it makes writing parsers easier.

See http://en.wikipedia.org/wiki/Chomsky_hierarchy

Mike Harris
  • 572
  • 3
  • 12
  • You bring up a good point about university projects often being different. It behooves him to clarify the exact requirements with his professor. – Karl Bielefeldt Jan 07 '14 at 19:02
2

The answer to your question is certainly Yes, both parsing and lexing rules can be and are specified using an EBNF (which is really just a more compact form of a BNF). However, in production quality compilers the next part of the answer is different.

Most languages have a grammar that is context free, and conforms to a set of rules to do with lookahead and backtracking. The commonest grammars are LL(1) and LR(1). LL(1) grammars allow a simple recursive descent grammar, often hand-coded, while LR(1) usually means a parser generator such as YACC. This part of the grammar goes down to tokens (terminals) but not lower.

The symbols are usually defined separately using an even simpler grammar, such as an operator grammar. [You can look up these terms for better definitions than I can give here.] The lexer that reads these symbols is typically responsible for most of the performance of the compiler so, in my experience, it is always hand-coded. LEX is clunky (and C only) and regex is too slow.

The point is to understand that the parsing rules drive the technology needed for your parser, and the lexing rules ditto for your lexer. The clear distinction between them is whether they apply to the use of tokens (terminals), or the construction of them.

This may not help your academic progress, but it matters if you go beyond toy projects.

david.pfx
  • 8,105
  • 2
  • 21
  • 44