本文已參與「新人創作禮」活動,一起開啟掘金創作之路.
The syntax analyzer is based on the lexical analyzer,How to use it is described abovepythonDesign a lexical analyzer,下面就來介紹如何使用pythonDesign a syntax analyzer.
創建一個使用 LL(1)方法或 LR(1)方法的語法分析程序.
輸入:
一個文本文檔,其中包含 2 型文法（上下文無關文法）的產生式集合
任務 1 詞法分析程序輸出的 token 令牌表
輸出:
YES 或 NO（源代碼字符串符合此 2 型文法,或者源代碼字符串不符合此 20 型文法
錯誤提示文件,如果有語法錯標示出錯行號,並給出大致的出錯原因
1. The role of grammatical analysis
Identify whether a string of word tokens given by lexical analysis is the correct sentence for a given grammar（程序）.
2. 分析方法
1）A top-down approach to deterministic analysis
從文法的開始符號出發,Consider how to use the current input symbol（單詞符號）It is uniquely determined which production is chosen to replace the corresponding nonterminal in the down derivation,Or how to construct a corresponding syntax tree.
2）自底向上優先分析
Scan the input string from left to right,And move the input symbols into a LIFO stack one by one,邊移入邊分析,The reduction occurs once the top-of-the-stack symbol string forms a handle to a sentence type or other reducible string,The result of the reduction is to pop the handle or other reducible string off the top of the stack,Instead, push the corresponding nonterminal onto the stack.
There are two methods of analysis from the bottom up：Operator-precedence analysis of sums LR 分析.
1. The design language and the language to be recognized
由 python language to write source programs,Analyze the lexically analyzed class C 語言的代碼
2. Parser code flow chart
syntax_analysis.py
LRDFANode 類和 LRDFA 類
LRDFANode The class represents each item set as a node
LRDFA A class representation consists of sets of items DFA
readSynaxGrammer(filename)函數
According to the composition of the input sentence 2 型文法,Convert it to a list of productions
getTerminatorsAndNon()函數
Get the set of terminals and nonterminals from the list of productions
具體實現：Traverse the list of productions,The left-hand side of each production must be all nonterminals,The set of terminals is obtained by subtracting the set of nonterminal symbols from the set of all symbols
getFirstSetForOne(cur_status, is_visit)函數
Find an element First 集
具體實現：
1. if the element is a terminator,那麼該元素在 First 集中
2. if the element is a nonterminal,and can derive a production guided by a terminal,then the terminator is in that element First 集中
3. if the element is a nonterminal,and can be deduced ε,ε 在該元素的 First 集中
getFirstSets()函數
使用 getFirstSetForOne(cur_status, is_visit)The function gets all elementsFirst 集
getClosure(cur_item, item_set)函數
The closure function that creates the itemsets
createLRTable()函數
創建 LR 分析表
具體實現：使用隊列,Start with an item set in an initial state,不斷搜索,Calculate conversion results,If there is no new state, it will be added to the tail of the queue
runOnLRTable(tokens)函數
分析 token Does the table conform to 2 The grammar specified by the type grammar
具體實現：Build a state stack and a symbol stack,使用 LR The analysis table does one of the following：移進、歸約、acc 和報錯
analyze(filename)函數
Enter what to analyze token 表進行分析
復制代碼
