How should I specify a grammar for a parser?

Question

I have been programming for many years, but one task that still takes me inordinately long is to specify a grammar for a parser, and even after this excessive effort, I'm never sure that the grammar I've come up with is good (by any reasonable measure of "good").

I don't expect that there is an algorithm for automating the process of specifying a grammar, but I hope that there are ways to structure the problem that eliminate much of the guesswork and trial-and-error of my current approach.

My first thought has been to read about parsers, and I've done some of this, but everything I've read on this subject takes the grammar as a given (or trivial enough that one can specify it by inspection), and focuses on the problem of translating this grammar into a parser. I'm interested in the problem immediately before: how to specify the grammar in the first place.

I'm primarily interested in the problem of specifying a grammar that formally represents a collection of concrete examples (positive and negative). This is different from the problem of designing a new syntax. Thanks to Macneil for pointing out this distinction.

I had never really appreciated the distinction between a grammar and a syntax, but now that I'm beginning to see it, I could sharpen my first clarification by saying that I'm primarily interested in the problem of specifying a grammar that will enforce a predefined syntax: it just so happens that in my case, the basis for this syntax is usually a collection of positive and negative examples.

How is the grammar specified for a parser? Is there a book or reference out there that's the de-facto standard for describing best practices, design methodologies, and other helpful information about specifying a grammar for a parser? What points, when reading about parser grammar, should I be focusing on?

Answer 1

From the sample files you will need to make decisions based on how much you want to generalize from those examples. Suppose you had the following three samples: (each is a separate file)

f() {}
f(a,b) {b+a}
int x = 5;

You could trivially specify two grammars that will accept these samples:

Trivial Grammar One:

start ::= f() {} | f(a,b) {b+a} | int x = 5;

Trivial Grammar Two:

start ::= tokens
tokens ::= token tokens | <empty>
token ::= identifier | literal | { | } | ( | ) | , | + | = | ;

The first one is trivial because it accepts only the three samples. The second one is trivial because it accepts everything that could possibly use those token types. [For this discussion I'm going to assume that you aren't concerned about the tokenizer design much: It's simple to assume identifiers, numbers, and punctuation as your tokens, and you could borrow any token set from any scripting language you'd like anyway.]

So, the procedure you'll need to follow is to start at the high level and decide "how many of each instance do I want to allow?" If a syntactic construct can make sense to repeat any number of times, such as methods in a class, you will want a rule with this form:

methods ::= method methods | empty

Which is better stated in EBNF as:

methods ::= {method}

It will probably be obvious when you only want zero or one instances (meaning that the construct is optional, as with the extends clause for a Java class), or when you want to allow one or more instances (as with a variable initializer in a declaration). You'll need to be mindful of issues like requiring a separator between elements (as with the , in an argument list), requiring a terminator after each element (as with the ; to separate statements), or requiring no separator or terminator (as the case with methods in a class).

If your language uses arithmetic expressions, it would be easy for you to copy from an existing language's precedence rules. It's best to stick to something well-known, like C's expressions rules, than going for something exotic, but only provided that all else is equal.

In addition to precedence issues (what gets parsed with each other) and repetition issues (how many of each element should occur, how are they separated?), you will also need to think about order: Must something always appear before another thing? If one thing is included, should another be excluded?

At this point, you may be tempted to grammatically enforce some rules, a rule such as if a Person's age is specified you don't want to allow their birthdate to be specified as well. While you can construct your grammar to do so, you may find it easier to enforce this with a "semantic check" pass after everything is parsed. This keeps the grammar simpler and, in my opinion, makes for better error messages for when the rule is violated.

Answer 2

Where can I learn how to specify the grammar for a parser?

For most parser generators, it's usually some variant of Backus-Naur's <nonterminal> ::= expression format. I'm going to go on the assumption that you're using something like that and not trying to build your parsers by hand. If you can produce a parser for a format where you've been given the syntax (I've included a sample problem below), specifying grammars isn't your problem.

What I think you're up against is divining syntax from a set of samples, which is really more pattern recognition than it is parsing. If you're having to resort to that, it means whoever is providing your data can't give you its syntax because they don't have a good handle on its format. If you have the option of pushing back and telling them to give you a formal definition, do it. It isn't fair for them to give you a vague problem if you could be held responsible for the consequences of a parser based on a deduced syntax accepting bad input or rejecting good input.

...I'm never sure that the grammar I've come up which is good (by any reasonable measure of "good").

"Good" in your situation would have to mean "parses the positives and rejects the negatives." Without any other formal specification of the syntax of your input file, the samples are your only test cases and you can't do any better than that. You could put your foot down and say that only the positive examples are good and reject anything else, but that probably isn't in the spirit of what you're trying to accomplish.

Under saner circumstances, testing a grammar is like testing anything else: you have to come up with enough test cases to exercise all variants of the nonterminals (and terminals, if they're being generated by a lexer).

---

Sample Problem

Write a grammar that will parse text files containing a list as defined by the rules below:

• A list consists of zero or more things.
• A thing consists of an identifier, an open brace, an item list and a closing brace.
• An _item_list_ consists of zero or more items.
• An item constsis of an identifier, an equal sign, another identifier and a semicolon.
• An identifier is a sequence of one or more of the characters A-Z, a-z, 0-9 or the underscore.
• Whitespace is ignored.

Example of input (all valid):

clank { foo = bar; baz = bear; }
clunk {
    quux =bletch;
    281_apple = OU812;
    He_Eats=Asparagus ; }

Answer 3

The answers by Macneil and Blrfl are great. I just want to add some comments about the beginning of the process.

A syntax is just a way to represent a program. So the syntax of your language should be determined by your answer to this question: What is a program?

You might say that a program is a collection of classes. Okay, that gives us

program ::= class*

as a starting point. Or you may have to write it

program ::= ε
         |  class program

Now, what is a class? It's got a name; an optional superclass specification; and a bunch of constructor, method, and field declarations. Also, you need some way of grouping a class into a single (unambiguous) unit, and that should involve some concessions to usability (eg, tag it with the reserved word class). Okay:

class ::= "class" identifier extends-clause? "{" class-member-decl * "}"

That's one notation ("concrete syntax") you could choose. Or you could just as easily decide on this:

class ::= "(" "class" identifier extends-clause "(" class-member-decl* ")" ")"

or

class ::= "class" identifier "=" "CLASS" extends-clause? class-member-decl* "END"

You've probably already made this decision implicitly, especially if you have examples, but I just want to reinforce the point: The structure of the syntax is determined by the structure of the programs it represents. That's what gets you past the "trivial grammars" from Macneil's answer. Example programs are still very important, though. They serve two purposes. First, they help you figure out, at the abstract level, what a program is. Second, they help you decide what concrete syntax you should use to represent your language's structure.

Once you've got the structure down, you should go back and deal with issues like allowing whitespace and comments, fixing ambiguities, etc. These are important, but they're secondary to the overall design, and they're highly dependent on the parsing technology you're using.

Finally, don't try to represent everything about your language in the grammar. For example, you may want to forbid certain kinds of unreachable code (eg, a statement after a return, like in Java). You probably shouldn't try to cram that into the grammar, because you'll either miss things (whoops, what if return is in braces, or what if both branches of an if statement return?) or you'll make your grammar way too complicated to manage. It's a context-sensitive constraint; write it as a separate pass. Another very common example of a context-sensitive constraint is a type system. You could reject expressions like 1 + "a" in the grammar, if you worked hard enough, but you couldn't reject 1 + x (where x has type string). So avoid half-baked restrictions in the grammar and do them correctly as a separate pass.