Ellerre

#+STARTUP: overview indent #+Title: EllErre - An LR automata generator #+EXPORT_EXCLUDE_TAGS: noexport

EllErre is designed to be an LR automata generator, with the following algorithms:

• [X] First Set
• [X] Follow Set
• [X] LR(0) automata / SLR(1) automata
• [X] LR(1) automata
• [X] LALR(1) automata
• [X] GraphViz automata representation
• [X] Mark initial and end states in the automata
• [X] Step by Step GraphViz automata representation for LR0/LR1
• [ ] Step by Step GraphViz automata representation for LALR1
• [ ] Detect shift/reduce and reduce/reduce conflicts
• [ ] LR Analysis for a given input

It is current in development.

For now, it calculates the First/Follow sets, the LR(0), LR(1) and LALR(1) automatas for a given grammar.

• Installation & Compilation

#+begin_src shell :results output sudo apt-get install git cmake build-essential flex bison libfl-dev; git clone https://github.com/schnorr/ellerre.git ; mkdir -p ellerre/b ; cd ellerre/b ; cmake .. ; make #+end_src

• If you want to visualize the automatas with graphviz #+begin_src shell :results output sudo apt-get install graphviz #+end_src

• Compilation only

#+begin_src shell :results output :exports both mkdir -p build ; cd build ; cmake .. ; make #+end_src

#+RESULTS: #+begin_example -- The C compiler identification is GNU 7.3.0 -- The CXX compiler identification is GNU 7.3.0 -- Check for working C compiler: /usr/bin/cc -- Check for working C compiler: /usr/bin/cc -- works -- Detecting C compiler ABI info -- Detecting C compiler ABI info - done -- Detecting C compile features -- Detecting C compile features - done -- Check for working CXX compiler: /usr/bin/c++ -- Check for working CXX compiler: /usr/bin/c++ -- works -- Detecting CXX compiler ABI info -- Detecting CXX compiler ABI info - done -- Detecting CXX compile features -- Detecting CXX compile features - done -- Found FLEX: /usr/bin/flex (found version "2.6.4") -- Found BISON: /usr/bin/bison (found version "3.0.4") -- Configuring done -- Generating done -- Build files have been written to: /tmp/ellerre/build [ 11%] [BISON][parser] Building parser with bison 3.0.4 [ 22%] [FLEX][scanner] Building scanner with flex 2.6.4 Scanning dependencies of target ellerre [ 33%] Building CXX object CMakeFiles/ellerre.dir/src/main.cc.o [ 44%] Building CXX object CMakeFiles/ellerre.dir/src/symbol.cc.o [ 55%] Building CXX object CMakeFiles/ellerre.dir/src/rule.cc.o [ 66%] Building CXX object CMakeFiles/ellerre.dir/src/grammar.cc.o [ 66%] [BISON][parser] Building parser with bison 3.0.4 [ 77%] Building CXX object CMakeFiles/ellerre.dir/scanner.cc.o [ 88%] Building CXX object CMakeFiles/ellerre.dir/parser.cc.o [100%] Linking CXX executable ellerre [100%] Built target ellerre #+end_example

• Execution ** First and Follow #+begin_src shell :results output :exports both cd build ./firstfollow < ../examples/ex1.ee #+end_src

#+RESULTS: #+begin_example Grammar with 3 rules and 4 symbols (2 non-terminals): S => A A A => a A A => b

First sets: S -- b a A -- b a

Follow sets: S -- $ A -- $ b a #+end_example

** LR(0) automata #+begin_src shell :results output :exports both cd build ./lr0 < ../examples/ex1.ee #+end_src

#+RESULTS: #+begin_example Grammar with 4 rules and 4 symbols (2 non-terminals): S' ⇒ S S ⇒ A A A ⇒ a A A ⇒ b

LR0 item set: S' ⇒ • S S' ⇒ S • S ⇒ • A A S ⇒ A • A S ⇒ A A • A ⇒ • a A A ⇒ a • A A ⇒ a A • A ⇒ • b A ⇒ b •

LR0 automata: State 0: S' ⇒ • S

S ⇒ • A A A ⇒ • a A A ⇒ • b Transitions: S ---> 1 A ---> 2 b ---> 3 a ---> 4

State 1: S' ⇒ S •

State 2: S ⇒ A • A

A ⇒ • a A A ⇒ • b Transitions: A ---> 5 b ---> 3 a ---> 4

State 3: A ⇒ b •

State 4: A ⇒ a • A

A ⇒ • a A A ⇒ • b Transitions: A ---> 6 b ---> 3 a ---> 4

State 5: S ⇒ A A •

State 6: A ⇒ a A •

#+end_example

** LR(1) automata #+begin_src shell :results output :exports both cd build ./lr1 < ../examples/ex1.ee #+end_src

#+RESULTS: #+begin_example Grammar with 4 rules and 4 symbols (2 non-terminals): S' => S S => A A A => a A A => b

First set: S -- b a A -- b a S' -- b a

Follow set: S -- $ A -- $ b a S' -- $

LR1 item set: S' => • S , $ S' => S • , $ S => • A A , $ S => A • A , $ S => A A • , $ A => • a A , $ A => • a A , b A => • a A , a A => a • A , $ A => a • A , b A => a • A , a A => a A • , $ A => a A • , b A => a A • , a A => • b , $ A => • b , b A => • b , a A => b • , $ A => b • , b A => b • , a

LR1 automata: State 0: S' => • S , $

S => • A A , $ A => • a A , b A => • a A , a A => • b , b A => • b , a Transitions: S ---> 1 A ---> 2 b ---> 3 a ---> 4

State 1: S' => S • , $

State 2: S => A • A , $

A => • a A , $ A => • b , $ Transitions: A ---> 5 b ---> 6 a ---> 7

State 3: A => b • , b A => b • , a

State 4: A => a • A , b A => a • A , a

A => • a A , b A => • a A , a A => • b , b A => • b , a Transitions: A ---> 8 b ---> 3 a ---> 4

State 5: S => A A • , $

State 6: A => b • , $

State 7: A => a • A , $

A => • a A , $ A => • b , $ Transitions: A ---> 9 b ---> 6 a ---> 7

State 8: A => a A • , b A => a A • , a

State 9: A => a A • , $

#+end_example

** LALR(1) automata #+begin_src shell :results output :exports both cd build ./lalr1 < ../examples/ex1.ee #+end_src

#+RESULTS: #+begin_example Grammar with 4 rules and 4 symbols (2 non-terminals): S' => S S => A A A => a A A => b

First set: S -- b a A -- b a S' -- b a

Follow set: S -- $ A -- $ b a S' -- $

LALR1 item set: S' => • S , $ S' => S • , $ S => • A A , $ S => A • A , $ S => A A • , $ A => • a A , $ A => • a A , b A => • a A , a A => a • A , $ A => a • A , b A => a • A , a A => a A • , $ A => a A • , b A => a A • , a A => • b , $ A => • b , b A => • b , a A => b • , $ A => b • , b A => b • , a

LALR1 automata: State 0: S' => • S , $

S => • A A , $ A => • a A , b A => • a A , a A => • b , b A => • b , a Transitions: S ---> 1 A ---> 2 b ---> 3 a ---> 4

State 1: S' => S • , $

State 2: S => A • A , $

A => • a A , $ A => • b , $ Transitions: A ---> 5 b ---> 3 a ---> 4

State 3: A => b • , $ A => b • , b A => b • , a

State 4: A => a • A , $ A => a • A , b A => a • A , a

A => • a A , $ A => • a A , b A => • a A , a A => • b , $ A => • b , b A => • b , a Transitions: A ---> 6 b ---> 3 a ---> 4

State 5: S => A A • , $

State 6: A => a A • , $ A => a A • , b A => a A • , a

#+end_example

• Generating the visual representation of the automata Each parser execution from EllErre generate a .dot file after its execution. The dot files are named after its parsing algorithm (LR0.dot, LR1.dot, and LALR1.dot).

This files can be used by tools like graphviz to generate a visual representation of the given LR automata.

** Example

*** Running the example The following execution generates the "LR0.dot" file, which describes the automata in the using the .dot syntax. #+begin_src shell :results output :exports both cd build ./lr0 < ../examples/ex1.ee >> /dev/null cat LR0.dot #+end_src

#+RESULTS: #+begin_example digraph g { graph [fontsize=30 labelloc="t" label="" splines=true overlap=false rankdir = "LR"]; ratio = auto; "state0" [ style = "filled" penwidth = 1 fillcolor = "white" fontname = "Courier New" shape = "Mrecord" label = <<table border="0" cellborder="0" cellpadding="3" bgcolor="white"> <tr><td bgcolor="black" align="center" colspan="2"><font color="white">State #0</font></td></tr> <tr><td align="left" port="r0"><font face="bold">S' ⇒ • S </font></td></tr> <tr><td align="left" port="r1"><font color="gray25" face="bold">S ⇒ • A A </font></td></tr> <tr><td align="left" port="r2"><font color="gray25" face="bold">A ⇒ • a A </font></td></tr> <tr><td align="left" port="r3"><font color="gray25" face="bold">A ⇒ • b </font></td></tr> </table>>];

"state1" [ style = "filled" penwidth = 1 fillcolor = "white" fontname = "Courier New" shape = "Mrecord" label = <<table border="0" cellborder="0" cellpadding="3" bgcolor="white">
	<tr><td bgcolor="black" align="center" colspan="2"><font color="white">State #1</font></td></tr>
	<tr><td align="left" port="r0"><font face="bold">S' ⇒ S • 

</font></td></tr> </table>>];

"state2" [ style = "filled" penwidth = 1 fillcolor = "white" fontname = "Courier New" shape = "Mrecord" label = <<table border="0" cellborder="0" cellpadding="3" bgcolor="white">
	<tr><td bgcolor="black" align="center" colspan="2"><font color="white">State #2</font></td></tr>
	<tr><td align="left" port="r0"><font face="bold">S ⇒ A • A 

</font></td></tr> <tr><td align="left" port="r1"><font color="gray25" face="bold">A ⇒ • a A </font></td></tr> <tr><td align="left" port="r2"><font color="gray25" face="bold">A ⇒ • b </font></td></tr> </table>>];

"state3" [ style = "filled" penwidth = 1 fillcolor = "white" fontname = "Courier New" shape = "Mrecord" label = <<table border="0" cellborder="0" cellpadding="3" bgcolor="white">
	<tr><td bgcolor="black" align="center" colspan="2"><font color="white">State #3</font></td></tr>
	<tr><td align="left" port="r0"><font face="bold">A ⇒ b • 

</font></td></tr> </table>>];

"state4" [ style = "filled" penwidth = 1 fillcolor = "white" fontname = "Courier New" shape = "Mrecord" label = <<table border="0" cellborder="0" cellpadding="3" bgcolor="white">
	<tr><td bgcolor="black" align="center" colspan="2"><font color="white">State #4</font></td></tr>
	<tr><td align="left" port="r0"><font face="bold">A ⇒ a • A 

</font></td></tr> <tr><td align="left" port="r1"><font color="gray25" face="bold">A ⇒ • a A </font></td></tr> <tr><td align="left" port="r2"><font color="gray25" face="bold">A ⇒ • b </font></td></tr> </table>>];

"state5" [ style = "filled"