Simple precedence grammar

A simple precedence grammar is a context-free formal grammar that can be parsed with a simple precedence parser.

Formal definition

Theory:

A grammar is said to be simple precedence grammar if it has no e-productions, no two productions have the same right side, and the relations <. s, = s,and .>s and disjoint. A SMP behaves eaxctly as OPM does, but NT’s are kept on the stack and enter into relations.

G = (N, Σ, P, S) is a simple precedence grammar if all the production rules in P comply with the following constraints:

• There are no erasing rules (ε-productions)
• There are no useless rules (unreachable symbols or unproductive rules)
• For each pair of symbols X, Y (X, Y $\in$ (N ∪ Σ)) there is only one Wirth-Weber precedence relation.
• G is uniquely inversible

Examples

Example 1

$S\to aSSb|c$

precedence table:

	S	a	b	c	$
S	${\dot {=}}$	$\lessdot$	${\dot {=}}$	$\lessdot$
a	${\dot {=}}$	$\lessdot$		$\lessdot$
b		$\gtrdot$		$\gtrdot$	$\gtrdot$
c		$\gtrdot$	$\gtrdot$	$\gtrdot$	$\gtrdot$
$		$\lessdot$		$\lessdot$

Ecternal links

• [1] at Clemson University