ZUCC_ Principles of compiling language and compilation_ Experiment 0607 grammar analysis ll analysis

Compiling language principle and compiling experiment report

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

Experimental content

One . read ppt Related content , Read textbook No 3 Chapter

1、 understand Nullable Set 、First Set 、 Follow Set Concept

1. Nullable Set ： A set of nonterminal characters of an empty string can be derived （ Belong to NULLABLE Collection means that the non terminator can be skipped without accepting any input ）
   • notes ： Only when the formulas on the right side of the production are all non terminators and can be derived ε, To add the symbol on the left of the production to NULLABLE Collection .
2. FIRST Set ：FIRST(α) Defined as from α The set of the first symbols of the derived sentence ,α Is an arbitrary string of grammatical symbols .
   • It can be understood as ：FIRST The set is the first character after the arrow , If this character is a non Terminator （ Capital ）, Just keep looking for something that this capital letter can deduce , Let's see if there is a non terminal character , If still , Keep looking , If it is a Terminator （ Lowercase letters ） Or empty string , Then put the terminator or empty string into the corresponding FIRST Collection .
3. Follow Set ： For non terminators A,FOLLOW(A) Is defined as the possibility of following in some sentence patterns A The set of terminations on the right .
   • It can be understood as ：
     • For the start symbol , Put... Directly # Added with the start symbol FOLLOW aggregate
     • Which symbol is required FOLLOW aggregate , Just find out all the formulas that contain this symbol , But only the symbol to the right of the arrow is useful
     • If this symbol is in the last , Take the symbol to the left of the arrow of the formula where this symbol is located FOLLOW Set add in
     • If the required symbol is followed by a non Terminator , Just take this non terminal FIRST Set minus empty string plus , Besides , If the non terminator after the required symbol is the same as the symbol to the left of the arrow , Put the arrow to the left FOLLOW Set is added to the required symbol FOLLOW Collection
     • If the required symbol is followed by a Terminator , Just add this terminator to FOLLOW Collection
     • The non terminator after the first production arrow , We should put the beginning symbol FOLLOW Sets are added to the corresponding FOLLOW Collection

• read NullableFirstFollow.pdf
• understand The construction method of each set
  • https://blog.csdn.net/YyjYsj/article/details/106379238

2、 understand Top down analysis , The difference between bottom-up analysis

• Top down analysis ：
  • The analysis tree is built from root to leaf nodes
  • Find the leftmost derivation sequence from the beginning symbol to the final sentence
  • Analyzer input Token Sequence
• Bottom up analysis ：
  • The analysis tree is built from the leaf node to the root node
  • Find the leftmost reduction sequence from the sentence to the starting symbol

3、 Understand deterministic top-down analysis ,LL(1) analysis

LL(1) Analysis method is also called prediction analysis method , yes A kind of Non recursive top-down without backtracking analysis .

• first L the second L, Numbers 1 What does each mean

  • 

• LL(1) Prediction analysis table construction , in And First Set Follow Relation of sets ,

  • 
  • 

• read NullableFirstFollow.pdf Understand the construction of analysis tables

4、 understand Calculate through the diagram First Set Follow Set method

• Graph calculation First Set
  • 
• Graph calculation Follow Set
  • 

5、 understand The correspondence between recursive descent analysis program and grammar

https://blog.csdn.net/qq_45180475/article/details/107845953

6、 By learning visualization tools , understand LL(1) Analysis of algorithm

• LL(1) visualization

  • 

• Online analysis tools grammophone

  • 

Two . With grammar

 S -> a | ^ |( T )
 T -> T , S | S

Please eliminate the left recursion of grammar .

3、 ... and . With grammar

E -> T | T ^ E
T -> int * T | ( E ) | ( S )
S -> int T

Please extract the left common factor of grammar .

Four . The following grammar is provided

S -> A
A -> B | A i B
B -> C | B + C
C -> ) A * | (

Decide if you can change the grammar to LL（1） Grammar

• Find the of each non terminator First Set And Follow Set

  • 

• structure LL（1） Forecast analysis table , Conclusion is given.

  • Revised as follows ：
    • 
    • 

5、 ... and . Given the following grammar

S -> + S S
S -> * S S
S -> a

The prediction analysis table of the grammar is given

Extract left common factor ：

S -> S' S | a
S' -> + | *

Use the prediction analyzer algorithm to analyze +*aaa, Judge whether the sentence belongs to the language of the grammar above .