1. Homepage
  2. Programming
  3. NCKU Compiler Construction - Homework 2. Syntactic Analysis (Parser)

NCKU Compiler Construction - Homework 2. Syntactic Analysis (Parser)

Engage in a Conversation
NCKUCompiler ConstructionYACCSyntactic AnalysisParser

112-2 國立成功大學編譯系統課程 CourseNana.COM

NCKU Compiler Construction - 2024 Spring CourseNana.COM

Homework 2. Syntactic Analysis (Parser) CourseNana.COM

Deadline: 2024/05/24 23:59:59 Late submissions are not accepted CourseNana.COM

作業規範 CourseNana.COM

  • ●  請不要攻擊我們的伺服器,否則這堂課會直接當掉 CourseNana.COM

  • ●  作業不接受任何形式的補交或遲交,請大家在截止前完成 CourseNana.COM

  • ●  作業截止後,我們會將所有同學的程式碼送到我們的比對系統 CourseNana.COM

    中,如有發生作業抄襲等情形,抄的人與被抄的人學期作業成 績 (40 %) 以 0 分計算 CourseNana.COM

本學期的作業配分 CourseNana.COM

這學期總共有 3 份作業,作業成績佔學期成績 40% CourseNana.COM

Homework 1 CourseNana.COM

  • ●  滿分 120, 平均 111 分 CourseNana.COM

  • ●  作業一的成績已經公告在 moodle CourseNana.COM

  • ●  對成績有疑問的請 4/13 晚上 11 點之前來信 逾期之後不再受理作業一的成績問題 CourseNana.COM

有人私底下跟我討論了這件事... CourseNana.COM

那我們改名成 C-- CourseNana.COM

編譯器的步驟 CourseNana.COM

Analysis-Synthesis Model CourseNana.COM

綜合來說,編譯的流程可以分成: 分析 Analysis ( front end ) CourseNana.COM

將程式拆成很多零件 CourseNana.COM

得到中間碼 intermediate representation (IR) 合成 Synthesis ( back end ) CourseNana.COM

利用中間碼組合出目標程式 最佳化 (可做可不做) CourseNana.COM

Analysis CourseNana.COM

Linear Analysis (Lexical Analysis)
掃描程式碼,將文字拆解成許多片段 ( Token ) CourseNana.COM

Hierarchical Analysis (Syntax Analysis) (Homework 2) 將這些 Token 組成文法 CourseNana.COM

Semantic Analysis
辨識語法錯誤,與型別問題 CourseNana.COM

Analysis CourseNana.COM

Syntactic Analysis (Parser) CourseNana.COM

  • ●  這是實作 Compiler 的第二個步驟! CourseNana.COM

  • ●  語法分析,就是 check 語法對不對的一個步驟 CourseNana.COM

  • ●  就像是英文有自己的文法,而 Parser 要做的事情就是 check CourseNana.COM

      程式碼的語法是否符合規定
    

Syntactic Analysis (Parser) CourseNana.COM

  • ●  作業一已經將程式碼切成很多 Token CourseNana.COM

  • ●  接下來我們要把 Token 照順序放入 Parser 解析語法 CourseNana.COM

你可以想像成我們要把這些 Token 組合成一個可以被 "理解" 的句子 CourseNana.COM

而要創造出一個句子,我們必須要先有語法 所以現在我們要制訂出一套文法標準 CourseNana.COM

Syntax Definition 語法定義 CourseNana.COM

每一個語言都有一個既定的 "規則"
這一個規則描述了程式語言在編寫時必須遵守的一些規範 我們通常把一個 "規則" 稱之為 文法 ( Grammar ) CourseNana.COM

Syntactic Analysis (Parser) CourseNana.COM

我們的目標是: CourseNana.COM

  • ○  將 Token 重新以正確的順序 (優先級) 輸出 CourseNana.COM

  • ○  簡易的判斷所有變數的可視範圍 (Scope) CourseNana.COM

  • ○  針對所有的 Scope Level 輸出一個表格,表格內有該 CourseNana.COM

         等級範圍內的所有變數資訊
    

Grammar Design 語法設計 CourseNana.COM

這個步驟我們最重要的是要建立出一個 Parser Tree 這一個樹要能表示解析所有的語法規則 CourseNana.COM

Grammar Design CourseNana.COM

建立 Parser Tree 的種類又分成兩種: CourseNana.COM

  • ○  Top-Down Parser (從根開始往下) CourseNana.COM

  • ○  Bottom-Up Parser (從葉子開始往上⻑)
    但在這一個作業我們會直接使用別人寫好的工具,這 CourseNana.COM

    一個工具會幫助我們更快的建立出 Parser Tree CourseNana.COM

Grammar Design (Yacc) CourseNana.COM

這邊特別科普一下:其實 BNF 就只是 CFG 所衍生出 來的一種特殊寫法而已,所以本質上還是以 CFG 為基 礎 CourseNana.COM

Grammar Design (Yacc) CourseNana.COM

  • ●  設計文法的一開始我們要跟 Lex 做搭配,先定義好所有 token 的屬性 CourseNana.COM

  • ●  這樣你設計文法的時候 Yacc 才會認得這個 token 是誰 CourseNana.COM

Grammar Design (Yacc) CourseNana.COM

  • ●  針對有 value 的 token 我們要背著他的屬性 CourseNana.COM

  • ●  所有 token 的型態在一開始 %union 要先定義好 CourseNana.COM

Grammar Design (Yacc) CourseNana.COM

如何設計文法?(BNF 格式) 下列文法可解析: CourseNana.COM

Grammar Design (Yacc) CourseNana.COM

我們解析文法的時候要搭配語意動作
輸出我們當前解析到的資訊,確保我們解析過程正確 只要在符號的右方使用大括號即可
當解析到 int 時就會執行語意動作 CourseNana.COM

語法制導翻譯方案 Syntax-Directed Translation Scheme CourseNana.COM

語意動作可以讓我們決定該動作執行的時間 (順序)
遍歷語法樹時,到達語意動作產生的節點才會執行該動作 CourseNana.COM

Grammar Design (Yacc) CourseNana.COM

  • ●  其餘更詳細的語法請參閱課程簡報 : D CourseNana.COM

  • ●  接下來我們講解我們希望你的 Yacc 可以輸出什麼 CourseNana.COM

Grammar Design (Yacc) - Output CourseNana.COM

  • ●  將 Token 重組後的順序與相關資訊 CourseNana.COM

  • ●  Symbol Table (等等會講為什麼正常來說需要這個東⻄) CourseNana.COM

Grammar Design (Yacc) - Output CourseNana.COM

將 Token 分析意思後,以正確的順序輸出 CourseNana.COM

Grammar Design (Yacc) - Output CourseNana.COM

各個符號的優先級可以參考維基百科上的 與我們平時寫的 C/C++ 的優先級一樣
或是參考我們的測資也可以! CourseNana.COM

輸出:可視範圍與生命週期

Grammar Design (Yacc) - Output CourseNana.COM

Grammar Design (Yacc) - Output CourseNana.COM

Insert:
遇到變數時,輸出他被 Insert 到的 scope 與 address CourseNana.COM

Grammar Design (Yacc) - Output CourseNana.COM

Grammar Design (Yacc) - Output CourseNana.COM

建議寫的時候參考解答輸出,更加了解每一個測試資料要求輸 出的東⻄! CourseNana.COM

每一個測試資料確認完輸出順序後再動手會比較好 >< CourseNana.COM

為什麼需要 Symbol Table? CourseNana.COM

整個編譯的過程都必須跟符號表 ( Symbol table ) 溝通 CourseNana.COM

Homework 2 作業上傳 CourseNana.COM

  • ●  請先 ssh 到 140.116.154.66 (非成大網路者,請使用 VPN) CourseNana.COM

  • ●  接著在你自己的資料夾中,clone 下方的 GitHub repo
    https://github.com/ColtenOuO/2024-Spring-NCKU-Compil CourseNana.COM

    erHW2/tree/main CourseNana.COM

進到 repo 資料夾後開始編寫 compiler.y CourseNana.COM

Homework 2 作業上傳 CourseNana.COM

  • ●  你的 compiler.l, compiler.y, Makefile 必須要放置在 ~/home/你的學號/2024-Spring-NCKU-CompilerHW2 CourseNana.COM

  • ●  這邊聲明一下,我們指的 clone 是指使用 git 指令將這一個 repo clone 下來,不要下載成 zip 後解壓縮 CourseNana.COM

Homework 2 作業上傳 CourseNana.COM

想先在自己系統寫的人請使用以下指令安裝環境 sudo apt install flex bison CourseNana.COM

Homework 2: Grading CourseNana.COM

本次作業滿分為 120 分
評分標準與上一個作業相同 CourseNana.COM

Homework 2: Subtasks CourseNana.COM

Homework 2: Subtasks CourseNana.COM

作業提示: 注意模稜兩可的情況 CourseNana.COM

此現象表示某一個文法可以被解讀成兩個以上的意思
就像是我們平時講的句子加上適當的標點符號可能會有很多不 CourseNana.COM

一樣的意思 CourseNana.COM

下雨天留客天留我不留 =>
下雨天留客,天留我不留。
下雨天留客,天留我?不留。 下雨天留客,天留我不?留。 CourseNana.COM

模稜兩可 Ambiguous CourseNana.COM

同一個文法具有兩個以上的文法樹 (Parse tree) CourseNana.COM

模稜兩可 Ambiguous CourseNana.COM

左圖可當作 ( 9 - 5 ) + 2,右圖可當作 9 - ( 5 + 2 ) CourseNana.COM

運算符號的結合性 CourseNana.COM

  • ●  依照數學的慣例,9 + 5 + 2 等價於 ( 9 + 5 ) + 2 CourseNana.COM

  • ●  當一個句子兩側都有運算符號時,我們需要制定一個性質 結合性 CourseNana.COM

    • ○  左結合 left-associative CourseNana.COM

    • ○  右結合 right-associative
      結合性幫助我們明確的知道每一個運算符號該用於誰 CourseNana.COM

+ 是左結合的,因此我們可以知道 9 + 5 的 + 是用於 9 身上 CourseNana.COM

運算符號的結合性 CourseNana.COM

作業提示: 注意運算符號的結合性 CourseNana.COM

有些符號屬於左結合,有些屬於右結合 CourseNana.COM

作業提示:有時候光依靠結合性無法解決問題

當一個文法具有許多運算符號時依舊無法解決模稜兩可的問題
結合性只能解決同一個運算符號重複出現造成的模稜兩可問題 CourseNana.COM

因此我們需要再處理不同運算符號之間的優先順序來解決問題 我們可以透過改寫文法來解決這樣的問題
這是最直接也最方便的方法 CourseNana.COM

總結:設計一個好的文法是很重要的! CourseNana.COM

作業提示:Symbol Table 善用一些資料結構 CourseNana.COM

你『可能』會用到: LinkedList CourseNana.COM

hash
也許他們可以讓你變輕鬆 CourseNana.COM

Homework 2: Challenge Subtask CourseNana.COM

讓你的 Parser 不會發生 Shift-Reduce Conflict 設計文法必須小心,避免發生模稜兩可 CourseNana.COM

Homework 2: 提醒 CourseNana.COM

  • ●  許多同學作業一切 token 的時候是有點硬做,把每一個變數 的名字都獨立成一個 token,這樣其實非常不好! CourseNana.COM

  • ●  你的 Compiler 會只能辨識那些變數名字!!! 請善用正則表達式
    這一次作業我們測資會 CourseNana.COM

    隨機生成變數名稱 CourseNana.COM

Homework 2: 請大家少用 remote-ssh CourseNana.COM

請善用 scp 指令,拜託QQ CourseNana.COM

Homework 2: 輸出目前只有 5 筆 CourseNana.COM

我們會盡快陸續把所有測資的答案補齊! 請大家再耐心稍候一下 >< CourseNana.COM

Homework 2: 重要時程 CourseNana.COM

作業繳交規定截止日:5/24 23:59:59 本學期退選截止日期:5/17 CourseNana.COM

CourseNana.COM

Homework 2: Final CourseNana.COM

  • ●  最後祝大家作業順利! Good luck & have fun CourseNana.COM

  • ●  測資是我們熬夜肝好幾個晚上用出來的,可能難免失手,如果 CourseNana.COM

    有覺得不對勁的地方可以跟我們說 >< CourseNana.COM

  • ●  f74114744@gs.ncku.edu.tw (資訊 115 陳俊安) CourseNana.COM

  • ●  f74114760@gs.ncku.edu.tw (資訊 115 張羿軒)  CourseNana.COM

Get in Touch with Our Experts

WeChat (微信) WeChat (微信)
Whatsapp WhatsApp
NCKU代写,Compiler Construction代写,YACC代写,Syntactic Analysis代写,Parser代写,NCKU代编,Compiler Construction代编,YACC代编,Syntactic Analysis代编,Parser代编,NCKU代考,Compiler Construction代考,YACC代考,Syntactic Analysis代考,Parser代考,NCKUhelp,Compiler Constructionhelp,YACChelp,Syntactic Analysishelp,Parserhelp,NCKU作业代写,Compiler Construction作业代写,YACC作业代写,Syntactic Analysis作业代写,Parser作业代写,NCKU编程代写,Compiler Construction编程代写,YACC编程代写,Syntactic Analysis编程代写,Parser编程代写,NCKUprogramming help,Compiler Constructionprogramming help,YACCprogramming help,Syntactic Analysisprogramming help,Parserprogramming help,NCKUassignment help,Compiler Constructionassignment help,YACCassignment help,Syntactic Analysisassignment help,Parserassignment help,NCKUsolution,Compiler Constructionsolution,YACCsolution,Syntactic Analysissolution,Parsersolution,