OPG_Parser

🔪 Operator Precedence Grammar Parser, in Coq.

Course Project for Compiler Principle (SJTU-CS308-2021)

Features

• Grammar Parser (in Haskell)
• Grammar Checker (in Coq)
• Operator Precedence Analysis Table Generator (in Coq)
• File IO and Pretty Printer (in Haskell)
• Shell (in Haskell)

Demo

The file "in1.txt" contains an operator precedence grammar, shown as follows:

E -> E + T | T
T -> T * F | F
F -> ( E ) | i

The program can parse the grammar and output its analysis table:

The file "in1.txt_output.md" contains the analysis table:

	+	*	(	)	i	$
+	>	<	<	>	<	>
*	>	>	<	>	<	>
(	<	<	<	=	<
)	>	>		>		>
i	>	>		>		>
$	<	<	<		<	=

How to build

To build the program, you need to install Colourista via stack

  stack install colourista

Then you can use GHCi/GHC to run/compile the program

  stack runhaskell Main.hs

or

  stack ghc -- -O2 Main.hs

or

  make

Tests

Test 1:

E -> E + T | T
T -> T * F | F
F -> ( E ) | i

Test 2:

E -> E + E | E * E | ( E ) | id

Test 3:

E -> E + T | T
T -> T * F | F
F -> ( E E ) | i

Here is the result:

License

MIT

Acknowledgements

• Colourista: Convenient interface for printing colourful messages
• Coq Proof Assistant: A formal proof management system