Micro Modula-2 Grammar

--Original--
LEFT-SIDE PROD.	RIGHT-SIDE PROD.
program_module		module_header imports block identifier "."
module_header		"MODULE" identifier ";"
imports			imports import | null
import			"FROM" identifier "IMPORT" identifier_list ";"
block			declarations "BEGIN" statement_sequence "END"
declarations		declarations declaration | null
declaration		"VAR" variable_decls | "TYPE" type_decls | procedure_declaration
variable_decls		varibale_decls variable_decl | null
variable_decl		identifier_list ":" type ";"
type_decls		type_decls type_decl | null
type_decl		identifier "=" type ";"
procedure_declaration	procedure_header block identifier ";"
procedure_header	"PROCEDURE" identifier "(" parameter_list ")" opt_func ";" | "PROCEDURE" identifier ";"
parameter_list		parameter_group | parameter_list ";" parameter_group
parameter_group	"VAR" identifier_list ":" type_name | identifier_list ":" type_name
opt_func		":" type_name
statement_sequence	statement | statement_sequence ";" statement
statement		null |
			identifier |
			identifier "(" expression_list ")" |
			identifier ":=" expression |
			identifier "[" simple_expression "]" ":=" expression |
			"WHILE" expression "DO" statement_sequence "END" |
			"REPEAT" statement_sequence "UNTIL" expression |
			"IF" expression "THEN" statement_sequence "END" |
			"IF" expression "THEN" statement_sequence "ELSE" statement_sequence "END" |
			"RETURN" expression
expression_list		expression | expression_list "," expression
expression		simple_expression | simple_expression rel_op simple_expression
simple_expression	add_op uns_simple_expression | uns_simple_expression
uns_simple_expression	term | uns_simple_expression add_op term
term			factor | term mul_op factor
factor			constant |
			identifier |
			identifier "(" expression_list ")" |
			identifier "[" simple_expression "]" |
			"(" expression ")"
constant			string_constant | number
number			integer | real
identifier_list		identifier | identifier_list "," identifier
type			type_name | "ARRAY" "[" integer ".." integer "]" "OF" type_name
type_name		identifier

--Original w/out Left Recursion--
LEFT-SIDE PROD.	RIGHT-SIDE PROD.
program_module		module_header imports block identifier "."
module_header		"MODULE" identifier ";"
imports			imports'
imports'			import imports'  | null
import			"FROM" identifier "IMPORT" identifier_list ";"
block			declarations "BEGIN" statement_sequence "END"
declarations		declarations'
declarations'		declaration declarations'  | null
declaration		"VAR" variable_decls | "TYPE" type_decls | procedure_declaration
variable_decls		varibale_decls'
variable_decls'		variable_decl varibale_decls'  | null
variable_decl		identifier_list ":" type ";"
type_decls		type_decls'
type_decls'		type_decl type_decls'  | null
type_decl		identifier "=" type ";"
procedure_declaration	procedure_header block identifier ";"
procedure_header	"PROCEDURE" identifier "(" parameter_list ")" opt_func ";" | "PROCEDURE" identifier ";"
parameter_list		parameter_group parameter_list'
parameter_list'		";" parameter_group parameter_list' | null
parameter_group	"VAR" identifier_list ":" type_name | identifier_list ":" type_name
opt_func		":" type_name
statement_sequence	statement statement_sequence'
statement_sequence'	";" statement statement_sequence' | null
statement		null |
			identifier |
			identifier "(" expression_list ")" |
			identifier ":=" expression |
			identifier "[" simple_expression "]" ":=" expression |
			"WHILE" expression "DO" statement_sequence "END" |
			"REPEAT" statement_sequence "UNTIL" expression |
			"IF" expression "THEN" statement_sequence "END" |
			"IF" expression "THEN" statement_sequence "ELSE" statement_sequence "END" |
			"RETURN" expression
expression_list		expression expression_list'
expression_list'		"," expression expression_list' | null
expression		simple_expression | simple_expression rel_op simple_expression
simple_expression	add_op uns_simple_expression | uns_simple_expression
uns_simple_expression	term uns_simple_expression'
uns_simple_expression'	add_op term uns_simple_expression' | null
term			factor term'
term'			mul_op factor term' | null
factor			constant |
			identifier |
			identifier "(" expression_list ")" |
			identifier "[" simple_expression "]" |
			"(" expression ")"
constant			string_constant | number
number			integer | real
identifier_list		identifier identifier_list'
identifier_list'		"," identifier identifier_list' | null
type			type_name | "ARRAY" "[" integer ".." integer "]" "OF" type_name
type_name		identifier

--Left Factored Original w/out Left Recursion--
LEFT-SIDE PROD.	RIGHT-SIDE PROD.
program_module		module_header imports block identifier "."
module_header		"MODULE" identifier ";"
imports			imports'
imports'			import imports'  | null
import			"FROM" identifier "IMPORT" identifier_list ";"
block			declarations "BEGIN" statement_sequence "END"
declarations		declarations'
declarations'		declaration declarations'  | null
declaration		"VAR" variable_decls | "TYPE" type_decls | procedure_declaration
variable_decls		varibale_decls'
variable_decls'		variable_decl varibale_decls'  | null
variable_decl		identifier_list ":" type ";"
type_decls		type_decls'
type_decls'		type_decl type_decls'  | null
type_decl		identifier "=" type ";"
procedure_declaration	procedure_header block identifier ";"
procedure_header	"PROCEDURE" identifier procedure_header'
procedure_header'	"(" parameter_list ")" opt_func ";" | ";"
parameter_list		parameter_group parameter_list'
parameter_list'		";" parameter_group parameter_list' | null
parameter_group	"VAR" identifier_list ":" type_name | identifier_list ":" type_name
opt_func		":" type_name
statement_sequence	statement statement_sequence'
statement_sequence'	";" statement statement_sequence' | null
statement		null |
			identifier statement'  |
			"WHILE" expression "DO" statement_sequence "END" |
			"REPEAT" statement_sequence "UNTIL" expression |
			"IF" expression "THEN" statement_sequence statement''  |
			"RETURN" expression
statement'		null |
			"(" expression_list ")" |
			":=" expression |
			[" simple_expression "]" ":=" expression
statement''		"END" |
			"ELSE" statement_sequence "END"
expression_list		expression expression_list'
expression_list'		"," expression expression_list' | null
expression		simple_expression expression'
expression'		rel_op simple_expression | null
simple_expression	add_op uns_simple_expression | uns_simple_expression
uns_simple_expression	term uns_simple_expression'
uns_simple_expression'	add_op term uns_simple_expression' | null
term			factor term'
term'			mul_op factor term' | null
factor			constant |
			identifier factor' |
			"(" expression ")"
factor'			null |
			"(" expression_list ")" |
			"[" simple_expression "]"
constant			string_constant | number
number			integer | real
identifier_list		identifier identifier_list'
identifier_list'		"," identifier identifier_list' | null
type			type_name | "ARRAY" "[" integer ".." integer "]" "OF" type_name
type_name		identifier

--Simplified, Left Factored Original w/out Left Recursion--
LEFT-SIDE PROD.	RIGHT-SIDE PROD.
program_module		module_header imports block identifier "."
module_header		"MODULE" identifier ";"
imports			import imports  | null
import			"FROM" identifier "IMPORT" identifier_list ";"
block			declarations "BEGIN" statement_sequence "END"
declarations		declaration declarations  | null
declaration		"VAR" variable_decls | "TYPE" type_decls | procedure_declaration
variable_decls		variable_decl varibale_decls  | null
variable_decl		identifier_list ":" type ";"
type_decls		type_decl type_decls  | null
type_decl		identifier "=" type ";"
procedure_declaration	procedure_header block identifier ";"
procedure_header	"PROCEDURE" identifier procedure_header'
procedure_header'	"(" parameter_list ")" opt_func ";" | ";"
parameter_list		parameter_group parameter_list'
parameter_list'		";" parameter_group parameter_list' | null
parameter_group	"VAR" identifier_list ":" type_name | identifier_list ":" type_name
opt_func		":" type_name
statement_sequence	statement statement_sequence'
statement_sequence'	";" statement statement_sequence' | null
statement		null |
			identifier statement'  |
			"WHILE" expression "DO" statement_sequence "END" |
			"REPEAT" statement_sequence "UNTIL" expression |
			"IF" expression "THEN" statement_sequence statement''  |
			"RETURN" expression
statement'		null |
			"(" expression_list ")" |
			":=" expression |
			[" simple_expression "]" ":=" expression
statement''		"END" |
			"ELSE" statement_sequence "END"
expression_list		expression expression_list'
expression_list'		"," expression expression_list' | null
expression		simple_expression expression'
expression'		rel_op simple_expression | null
simple_expression	add_op uns_simple_expression | uns_simple_expression
uns_simple_expression	term uns_simple_expression'
uns_simple_expression'	add_op term uns_simple_expression' | null
term			factor term'
term'			mul_op factor term' | null
factor			constant |
			identifier factor' |
			"(" expression ")"
factor'			null |
			"(" expression_list ")" |
			"[" simple_expression "]"
constant			string_constant | number
number			integer | real
identifier_list		identifier identifier_list'
identifier_list'		"," identifier identifier_list' | null
type			type_name | "ARRAY" "[" integer ".." integer "]" "OF" type_name
type_name		identifier

--FIRSTs for the Modified Grammar--
PRODUCTION		FIRST RESULT
program_module		FIRST(module_header) = 
			"MODULE"
module_header		"MODULE"
imports			FIRST(import) , null = 
			"FROM" , null
import			"FROM"
block			FIRST(declarations) = 
			FIRST(declaration) , null = 
			"VAR" , "TYPE" , FIRST(procedure_declaration) , FIRST("BEGIN") = 
			"VAR" , "TYPE" , FIRST(procedure_header) , "BEGIN" = 
			"VAR" , "TYPE" , "PROCEDURE" , "BEGIN"
declarations		FIRST(declaration) , null = 
			"VAR" , "TYPE" , FIRST(procedure_declaration) , null = 
			"VAR" , "TYPE" , FIRST(procedure_header) , null = 
			"VAR" , "TYPE" , "PROCEDURE" , null
declaration		"VAR" , "TYPE" , FIRST(procedure_declaration) = 
			"VAR" , "TYPE" , FIRST(procedure_header)  = 
			"VAR" , "TYPE" , "PROCEDURE"
variable_decls		FIRST(variable_decl) , null = 
			FIRST(identifier_list) , null = 
			identifier , null
variable_decl		FIRST(identifier_list) = 
			identifier
type_decls		FIRST(type_decl) , null = 
			identifier , null
type_decl		identifier
procedure_declaration	FIRST(procedure_header) =
			"PROCEDURE"
procedure_header	"PROCEDURE"
procedure_header'	"(" , ";"
parameter_list		FIRST(parameter_group) = 
			"VAR" , FIRST(identifier_list) = 
			"VAR" , identifier
parameter_list'		";" , null
parameter_group	"VAR" , FIRST(identifier_list) = 
			"VAR" , identifier
opt_func		":"
statement_sequence	FIRST(statement) = 
			null , identifier , "WHILE" , "REPEAT" , "IF", "RETURN" = 
			FIRST(statement_sequence) , identifier , "WHILE" , "REPEAT" , "IF", "RETURN" = 
			null , ";" , identifier , "WHILE" , "REPEAT" , "IF", "RETURN"
statement_sequence'	";" , null
statement		null , identifier , "WHILE" , "REPEAT" , "IF", "RETURN"
statement'		null , "(" , ":=", "["
statement''		"END" , "ELSE"
expression_list		FIRST(expression)  = 
			FIRST(simple_expression) = 
			add_op , FIRST(uns_simple_expression) =
			add_op , FIRST(term) =
			add_op , FIRST(factor) =
			add_op , FIRST(constant) , identifier , "(" =
			add_op , string_constant , FIRST(number) , identifier , "(" =
			add_op , string_constant , integer , real , identifier , "("
expression_list'		"," , null
expression		FIRST(simple_expression) = 
			add_op , FIRST(uns_simple_expression) =
			add_op , FIRST(term) =
			add_op , FIRST(factor) =
			add_op , FIRST(constant) , identifier , "(" =
			add_op , string_constant , FIRST(number) , identifier , "(" =
			add_op , string_constant , integer , real , identifier , "(" =
expression'		rel_op , null
simple_expression	add_op , FIRST(uns_simple_expression) =
			add_op , FIRST(term) =
			add_op , FIRST(factor) =
			add_op , FIRST(constant) , identifier , "(" =
			add_op , string_constant , FIRST(number) , identifier , "(" =
			add_op , string_constant , integer , real , identifier , "(" =
uns_simple_expression	FIRST(term) =
			FIRST(factor) =
			FIRST(constant) , identifier , "(" =
			string_constant , FIRST(number) , identifier , "(" =
			string_constant , integer , real , identifier , "("
uns_simple_expression'	add_op , null
term			FIRST(factor) =
			FIRST(constant) , identifier , "(" =
			string_constant , FIRST(number) , identifier , "(" =
			string_constant , integer , real , identifier , "(" =
term'			mul_op , null
factor			FIRST(constant) , identifier , "(" =
			string_constant , FIRST(number) , identifier , "(" =
			string_constant , integer , real , identifier , "(" =
factor'			null , "(" , "["
constant			string_constant , FIRST(number)
			string_constant , integer , real
number			integer , real
identifier_list		identifier
identifier_list'		"," , null
type			FIRST(type_name) , "ARRAY" = 
			identifier , "ARRAY"
type_name		identifier