ZUCC_ Principles of compiling language and compilation_ Experiment 08 parsing LR parsing

Compiling language principle and compiling experiment report

Course name	Programming language principle and compilation
Experimental projects	Syntax analysis LR analysis

Experimental content

read ppt, Read textbook No 3 Chapter

understand LR（0） DFA The building process of

Introduction structure ：

• structure NFA

  • 

• structure DFA

  • The subset construction method is used to determine the result DFA

Direct structure ：

• structure DFA

  • stay LR(0) Add augmented grammar on the basis of grammar , Make the analyzer have only one receive state

  • In a certain LR(0) All of grammar LR(0) In the project , There is a duplicate item in the item with non terminator after the dot , These sets of items are called Project set closure , Corresponding DFA A state of （ Use CLOSURE() function ）

  • Start with augmented grammar , Traverse DFA The successor of each item in the status LR(0) project （ Use GOTO() function ）, Each traversal is treated as a state , And use this symbol to link . for example ：

  • If you encounter reduced items , Then the branch ends ; When it's all over , structure DFA end

Understand how to learn from DFA State diagram , Conduct LR Construction of analysis table

• according to DFA The number of nodes in the analysis table determines the number of states in the analysis table
• from DFA Start node starts traversal , If you encounter a Terminator , Then for ACTION Jump ; If you encounter a non Terminator , Then for GOTO Jump
• about ACTION surface , If DFA The actions in are reduced items , Then for rn（ reduction ） operation ; If it is not a reduced item , Then for sn（ move ） operation

The teaching material p50 3.4.3 Understand the causes of conflict

1. Move in / Conflict of reduction ： There are multiple items in one state , First, it is required to perform the move in operation , First, it requires the implementation of reduction projects
2. reduction / Conflict of reduction ： There are multiple items in one state , The two require different reduction operations
3. Mixed conflict ： Mix move in / Conflict of reduction 、 reduction / Conflict of reduction

If there is no conflict, it is LR(0) Grammar , Otherwise LR(1) Grammar

p51 understand chart 3-13LR State table , Find the conflict item

In state 9、11、13、15 There is a move in / Conflict of reduction

Find one Action Table（ Action sheet ） ,Goto Table（ State transition table ） The definition of

The teaching material p50 3.4.2. Priority guidance

Understand in the grammar documentation , How priority is assigned

What is left / Right Union / Uncombined , How to declare in the syntax file p53

• + and - Is left associative and has the same priority ：* and / Are left associative and their priority is higher than ＋;^ Is right combined and has the highest priority ：= and != A combination of right and wrong , Their priority is lower than ＋
• utilize LR(1) To limit , Only when the next input is a predictor can the reduction operation be performed

How to use %prec instructions , Customize the priority of a rule p53

• When rules and words have equal priority , use %1eft The indicated priority is in favor of reduction ,%right Indicated bias to move in , And by the %nonassoo What is indicated causes a wrong action .

http://mdaines.github.io/grammophone/# Check your homework

The following grammar is provided

S -> S A b .
S -> a c b .
A -> b B c .
A -> b c .
B -> b a .
B -> A c .

The contents of the analysis stack are as follows , Please write down what the reducible string is （▽ Indicates the bottom of the stack ）：

(a)▽SSAb
(b)▽SSbbc
(c)▽SbBc
(d)▽Sbbc

(a) Can be reduced to string ：SAb
(b) Can be reduced to string ：bc
(c) Can be reduced to string ：bBc
(d) Can be reduced to string ：bc

The following input strings are provided , Please use 2 Grammar in , use shift/reduce Analyze the following string .

Please press ppt in Construct table , List analysis stacks , Input stream , shift/reduce operation The content of

(a) acb
(b) acbbcb
(c) acbbbacb
(d) acbbbcccb
(e) acbbcbbcb

• step	Stack	Input string
  0	$	acb$
  2	$a	cb$
  5	$ac	b$
  11	$acb	$
  acc	$	$

  step	Stack	Input string
  0	$	acbbcb$
  2	$a	cbbcb$
  5	$ac	bbcb$
  11	$acb	bcb$
  0	$	bcb$
  1	$S	bcb$
  4	$Sb	cb$
  8	$Sbc	b$
  1	$SA	b$
  3	$SA	b$
  6	$SAb	$
  acc	$	$

  step	Stack	Input string
  0	$	acbbbacb$
  2	$a	cbbbacb$
  5	$ac	bbbacb$
  11	$acb	bbacb$
  0	$	bbacb$
  1	$S	bbacb$
  4	$Sb	bacb$
  9	$Sbb	acb$
  13	$Sbba	cb$
  4	$Sb	cb$
  7	$SbB	cb$
  12	$SbBc	b$
  1	$S	b$
  3	$SA	b$
  6	$SAb	$
  acc	$	$

  step	Stack	Input string
  0	$	acbbbcccb$
  2	$a	cbbbcccb$
  5	$ac	bbbcccb$
  11	$acb	bbcccb$
  0	$	bbcccb$
  1	$S	bbcccb$
  4	$Sb	bcccb$
  9	$Sbb	cccb$
  15	$Sbbc	ccb$
  4	$Sb	ccb$
  10	$SbA	ccb$
  16	$SbAc	cb$
  4	$Sb	cb$
  7	$SbB	cb$
  12	$SbBc	b$
  1	$S	b$
  3	$SA	b$
  6	$SAb	$
  acc	$	$

  step	Stack	Input string
  0	$	acbbcbbcb$
  2	$a	cbbcbbcb$
  5	$ac	bbcbbcb$
  11	$acb	bcbbcb$
  0	$	bcbbcb$
  1	$S	bcbbcb$
  4	$Sb	cbbcb$
  8	$Sbc	bbcb$
  1	$S	bbcb$
  3	$SA	bbcb$
  6	$SAb	bcb$
  0	$	bcb$
  1	$S	bcb$
  4	$Sb	cb$
  8	$Sbc	b$
  1	$S	b$
  3	$SA	b$
  6	$SAb	$
  acc	$	$

The following grammar and input string are provided , Please indicate whether there is shift/reduce Conflict perhaps reduce/reduce Conflict

S -> S a b .
S -> b A .
A -> b b .
A -> b A .
A -> b b c .
A -> c .

Input string

(a) b c
(b) b b c a b
(c) b a c b

• step	Stack	Input string
  0	$	bc$
  2	$b	c$
  6	$bc	$
  2	$b	$
  4	$bA	$
  acc	$	$

  step	Stack	Input string
  0	$	bbcab$
  2	$b	bcab$
  5	$bb	cab$
  6	$bbc	ab$
  5	$bb	ab$
  9	$bbA	ab$
  2	$b	ab$
  4	$bA	ab$
  0	$	ab$
  1	$S	ab$
  3	$Sa	b$
  7	$Sab	$
  acc	$	$

  step	Stack	Input string
  0	$	bacb$
  2	$b	acb$
  err

There is reduce/reduce Conflict , But the situation 3 It is not because of this error , It is a non production error report

read lecture03.p31.fsyacc.pdf p31 page master fslex,fsyacc Use

read calcvar in

• Lexical description lexer.fsl
• Syntax description parser.fsy
• Debug running code
• Understand how priority guidance is written
  • read ReadME

plzoofs calcvar project , to fsyacc Tools add -v Parameters , View the generated parser LR State table

// calcvar.fsproj 
<FsYacc *Include*="parser.fsy">
    <OtherFlags> -v --module Parser</OtherFlags>
</FsYacc>

Pay attention to... In a specific state

• action table
• goto table

read Fun In language

• Lexical description FunLex.fsl
• Syntax description FunPar.fsy
• Debug running code
• ditto fsyacc Tools add -v see LR Analysis status table

read MicroC parsers

• https://gitee.com/sigcc/plzoofs/blob/master/microc/CPar.fsy
• because C The pointer to language , Array parsing is complicated , Advanced functional programming skills are used to construct the syntax tree
• We slowly understand

Fsharp Reference cases （ Optional ）

• Postfix/ The suffix type operation 1 2 + 3 *
• Usql/ sql Language grammar analysis