murraycu/murrayc-compiler-experiments

Code experiments to exercise ideas while reading "Engineering a Compiler".

murrayc-compiler-experiments's Issues

LR(1) parser cannot parse the Signed Binary Number grammar from chapter 4

The source code
https://github.com/murraycu/murrayc-compiler-experiments/blob/master/src/chapter_03/section_3_4_2_bottom_up_lr1_parser_with_generated_tables.cc
has some commented-out test code to use the SBN grammar from chapter 4, but it fails with input of
"+11"
like so (with the debugging code uncommented in the parser):

State: 0, symbol: +: 
  Shift: Moving to state 3
State: 3, symbol: 1: 
  Reduce: by rule: 6 (Sign -> + )
  Popping 1 from stack.
  Moving from previous state 0 to next state 2
State: 2, symbol: 1: 
  Shift: Moving to state 6
State: 6, symbol: 1: 
  State 6 has no action for symbol 1
    parsed so far: + 1 

These are the rules, and the action and goto tables (from print_action_and_goto_tables()):

Rules:
0: Bit -> 0
1: Bit -> 1
2: Goal -> Number
3: List -> Bit
4: List -> List, Bit
5: Number -> Sign, List
6: Sign -> +
7: Sign -> -

Action Table:
0:
  +: s3
  -: s4

1:
  eof: a0

2:
  0: s5
  1: s6

3:
  0: r6 (Sign -> +)
  1: r6 (Sign -> +)

4:
  0: r7 (Sign -> -)
  1: r7 (Sign -> -)

5:
  eof: r0 (Bit -> 0)

6:
  eof: r1 (Bit -> 1)

7:
  0: r3 (List -> Bit)
  1: r3 (List -> Bit)
  eof: r3 (List -> Bit)

8:
  0: s9
  1: s10
  eof: r5 (Number -> Sign, List)

9:
  0: r0 (Bit -> 0)
  1: r0 (Bit -> 0)
  eof: r0 (Bit -> 0)

10:
  0: r1 (Bit -> 1)
  1: r1 (Bit -> 1)
  eof: r1 (Bit -> 1)

11:
  0: r4 (List -> List, Bit)
  1: r4 (List -> List, Bit)
  eof: r4 (List -> List, Bit)


Goto Table:
0:
  Number: 1
  Sign: 2

2:
  Bit: 7
  List: 8

8:
  Bit: 11

So, the transition from state 2

{Bit ->  . 0}, eof
{Bit ->  . 1}, eof
{List ->  . Bit}, 0
{List ->  . Bit}, 1
{List ->  . Bit}, eof
{List ->  . List, Bit}, 0
{List ->  . List, Bit}, 1
{List ->  . List, Bit}, eof
{Number -> Sign . , List}, eof

on symbol "1" (probably via {List -> . Bit }, 1) takes us to state 6:

{Bit -> 1 .}, eof

which has no suitable transition.

section_2_4_4 and some questions

cpchung:murrayc-compiler-experiments$ ./section_2_4_4_minimal_dfa_with_hopcrofts_algorithm
Current partitions: {{s0, s1, s2, s4}, {s3, s5}}
Splitting on partition: {s0, s1, s2, s4}
Segmentation fault (core dumped)

I am very interested in the set of build tools you were using in this repo. Would you please shed some light some good starting point to know what those build tools are doing? I am still not clear how you generated the Makefile and what are the useful commands to really use it in full potential.