Context Free, Linear Grammar, Operator Grammar

Linear Grammar

A linear grammar has at most one nonterminal on the right side of any production.

A linear grammar need not be regular, as shown by the following example, which generates 0ⁿ1ⁿ.

s → 0t | E
t → s1

Operator Grammar

An operator grammar has no consecutive nonterminals in the right side of any production. It is so named because operators (terminals) stand between operands (nonterminals). For instance, + is an operator in most computer languages, and it is a terminal in the associated grammar. It separates expressions, which are nonterminals in the associated grammar.

Operator grammars, the grammars of computer science, are relatively easy to parse. Of course the C grammar admits adjacent nonterminals, and is not truly an operator grammar, but the section that analyzes arithmetic expressions, which is the bulk of the grammar, avoids adjacent nonterminals, so that tools such as yacc can generate a parser for the compiler, without a flurry of shift/reduce or reduce/reduce conflicts.

I could write at length about operator precedence, and look-ahead parsers, and their applications in computer science, but for now, I'm going to avoid such distractions. We are exploring formal language theory, on the path to turing machines and decidability. My apologies to the computer science folks, but you won't find anything more on compilers or real-world parsers here. I can't be everything to everyone.