递归下降法 1 递归下降法语法分析原理 递归子程序方法/递归下降法 对每个非终极符按其产生式结构产生相应语法分析子程序。

Slides:



Advertisements
Similar presentations
達悟族報告 作者 : 林琪崴, 許原碩 座號 :13 號,14 號 原碩負責 : 簡介, 傳說, 圖驣, 達悟族飛魚季, 琪崴 : 地理位置, 土地利用方式, 飲食文化, 豐收祭.
Advertisements

主讲:张天明 影像艺术工程师. 声音的聆听 指出听到的是什么物体发出的声音,这一 声音是在什么样的空间环境中传播的。 一、 答案: 1 、打气筒打气的声音 2 、手打打气筒给足球打气的声音 3 、手打打气筒给自行车轮胎打气的声音 4 、七次(七声)打气筒打气的声音 5 、(气流)摩擦的声音 6 、猪在发急时的叫声.
概念導向命題技巧與試題分析 臺灣師大地理系 陳國川. 教學評量是一種『抽樣調查』 實施教學評量時,需具備二項條件: 其一,瞭解命題的理論及其實踐的方法; 其二,瞭解各種題型的功能與命題方式。 壹、前言.
高峰植物園行前解說 2005/12/07 By 羽明. 陽性先驅物種 陽性植物 --- 陽光需求量大 陰性 ( 或耐蔭性 ) 植物 --- 陽光需求量少, 或 日照太強反而無法生存 先驅植物 --- 森林大火或土石流地震後產生的 裸露空地, 先生長出來的植物.
報 告 人 : 胡 嘉 琪 ˙ˇ˙ 、 王 紫 庭 = ˇ = 台灣夜市文化 作者: 郭明澤‧私立明道高中‧綜二 4 班 馬炯修‧私立明道高中‧綜二 4 班.
5 ˙ 1 第五章 生物的協調作用 5 ‧ 1 神經系統. 5 ˙ 1 人體的神經系統 1. 協調動物生理反應的系統: 神經 系統、 內分 泌 系統。 2. 神經系統負責 統整 和 協調 。分為 中樞 神經 和 周圍 神經。 (1) 中樞神經包括 腦 和 脊髓 。 (2) 周圍 神經包括 腦神經 和.
从《西游》看大学生的成长 主讲人:颜廷学 时间: 地点:演艺大楼流行剧场.
新员工培训 设计部 思安新能源股份有限公司 主讲人: 韩少华 时 间:
前言:河流的主要功能 1. 交通運輸 優點-運費低廉,維護費用低 缺點-速度慢,裝載費時,不能到達生產區或消費區 的末端,需要轉載。 尚受到河流網路,河口位置,水量變化,河床 狀況,冰封時期 2. 水資源系統.
幽夢影~張潮 小佑子工作室 關於《幽夢影》 作者張潮,記寫他個人對人生世事之體驗透悟的 書。 書中文字,全為「語錄」形式,屬於格言,也是 最精鍊的隨筆。 全書可分為九卷:論才子佳人、論人與人生、論 朋友知己、論讀書、論閒情逸趣、論立身處世、 談文論藝、論四時佳景、論花鳥蟲魚。
成人高考高起点 语文 冲刺班 主讲老师:邓君媚. 复习指导 高考语文含四大块内容: 语言知识和语言表达,古代诗文阅读,现 代文阅读,写作。 在全面复习的前提下,按照《考试大纲》 的要求,要做好思路整理,建立高考的整体框 架的工作。认真归纳整理基础知识、培养基本 能力,复习做到有的放矢。 复习指导.
老师,我可以不 爱 吗? 山东省淄博市张店区实验中学 杜桂兰 星期一的早晨,我紧张而又兴奋,因为 我的赛教课就要开始了。 这是一次级别很 高 的竞赛。
财政部 国家税务总局 中国人民银行(央行) 银监会 证监会 保监会. 法定存款准备金率 利率 税率 政府投资 楼继伟,周小川,易纲.
油蔴菜籽 指導老師:陳瑜霞 學生: 商設一甲 謝旻璇 車輛三乙 許勝傑 工管四甲 彭凱雲. 作者介紹: 廖輝英( 1948 年生)臺大中文系畢業。 從初三開始寫作,早期作品多以散文為主,大四 畢業時才暫時封筆。畢業後進了廣告界,成為廣 告文案好手,後為企畫主管,在廣告界縱橫十餘 年,也曾任職於建設公司,辦過社區報高雄一周。
蘭嶼情人洞傳說 林庭羽製 林庭羽製. 台灣的蘭花特別多,台灣有個蘭 嶼島,島上面的蘭花更多.所以 叫蘭嶼.這裡留下了動人的傳說。
職業訪談報告. 成員 : 鐘怡君 劉沛君 謝明達 賴映辰.
南台科大幼保實習課程 見習幼兒園心得報告 夜四技幼保四甲 998i0021 黃欣婷.
第一章 生殖 1‧2 無性生殖.
高教三十条 — 科技创新能力提升 科技创新能力提升工程方案起草小组 2013年7月4日.
你不可不知之 十二年國教二三事 教務主任:傅瑞琪.
鞋 楦 的 材 質.
最古怪的15種動物.
走! 一起去拜訪筏子溪.
台灣文學館之旅.
單車環島之旅 組員: 495D0072 胡閎智 495D0074 何冠緯 495D0020 王怡雯 495D0047 葉亭君
 耕地分割 及 執 行 內政部地政司 視察:林玲女.
~完備、周密、迅速 ~ 行政院農業部畜產試驗所
建筑设计基础讲义 (02-1) 建筑水彩渲染.
現代文學導讀 (中國現代散文發展的歷史軌道)
谨以此文—— 送给所有的人.
方 孝 孺 指喻.
保護地球人人有責:我能做的事 若想讓地球、人類社會明天會更好的話,可以考慮日常生活中採取什麼綠色行動,逐步恢復按上天設計大自然規定的方式做人,從而減少個人的「生態足印」,爭取可以延續的未來。 
小 王 子 <第六組> 組長: 謝汶芳 組員: 劉佳蓉 曹展愛 陳建妏
據說: 烏鴉有四種--- 巨烏 祥烏 鳳烏 慈烏~ 知恩 感恩 報恩.
桃園傅小弟遭刺青施虐事件 指導老師:高家斌 班級:幼保四甲 姓名與學號: 496I0004 程千芸、496I0010 林昀嫻
北科大學士學位 冷凍空調 甲、乙、丙 級技術士 三年工作經驗 大一階段 專精訓練 大三階段 回流訓練.
9.2.2 会计基本法律制度 一、会计机构和会计人员制度 二、会计核算制度
指導教授:林劭仁老師 組員:范紋綺、王宣惠、蔡雅玲 王思樺、陳可馨、吳芷容.
歡欣鼓舞過新年之四-跟年有關的故事 蘇澳國小 三年三班導師 張怡玲.
淺談中醫養生保健之道 國立中正大學醫務室 中醫科 楊明穎 醫師 中國醫藥學院 醫學士中醫師 高雄醫學院 藥學士藥師
只要有心 機器都可以成為食神 機電三甲  陳保翔  宓芳頡  雷家翔.
北極熊 華德學校 姓名:黄景山.
數學家 阿基米德 6C 李俊熙.
一般情况碰撞 1 完全弹性碰撞 动量和机械能均守恒 2 非弹性碰撞 动量守恒,机械能不守恒 3 完全非弹性碰撞 动量守恒,机械能不守恒.
目錄 99年『 84電腦及相關服務』案件統計 機關端:資訊服務價格資料登錄流程 機關端及廠商端:資訊服務價格資料查詢流程
十堰管理部党委中心组“三严三实” 第三阶段专题学习
公共選擇理論 實踐大學 指導老師:林信雄.
孩子的心,我懂 怀仁全人发展中心 任兆璋 着.
校园信息管理系统 河北科技大学网络中心 2000/4/10.
徵收苗栗市福全段147、1588及文心段10、11地號等4筆土地之
讲 义 大家好!根据局领导的指示,在局会计科和各业务科室的安排下,我给各位简要介绍支付中心的工作职能和集中支付的业务流程。这样使我们之间沟通更融洽,便于我们为预算单位提供更优质的服务。 下面我主要从三方面介绍集中支付业务,一是网上支付系统,二是集中支付业务流程及规定等,
课程改革与教师成长 泰安市岱岳区教研室 程同森.
全球暖化 想知道全球暖化的嚴重性嗎? 那就繼續看下去吧!! 組員:陳儀君60524 蘇鈺祺60526 于玉琳60528 林宥嫻60521.
中国人民公安大学经费管理办法(试行) 第一章总则 第四条:“一支笔” “一支笔”--仅指单位主要负责人。负责对本 单位的经费进行审核审批。
我国的人民民主专政.
自上而下分析 4.4.
自上而下分析 4.4.
编译原理课程设计.
编译原理实践 5.给定语法的语法分析程序构造.
LL分析法 LL分析法的分析器由一张预测分析表(LL(1)分析表),一个控制程序(表驱动程序)及一分析栈组成 输入
编译原理 第四章 语法分析—自上而下分析 编译原理.
第四章 自顶向下语法分析方法 语法分析的主要工作:是识别由词法分析给出的单词 序列是否是给定的正确句子(程序)。
教科版六年级下册第一单元第4课 怎样放得更大 莲都区天宁小学 陈建秋.
微信商城系统操作说明 色卡会智能门店.
编译原理课程设计 2017年4月.
問題解決與流程圖 高慧君 台北市立南港高中 2006年12月22日.
第四章 语法分析 南京大学计算机系 戴新宇
數學遊戲二 大象轉彎.
大綱 一.受試者之禮券/禮品所得稅規範 二.範例介紹 三.自主管理 四.財務室提醒.
手机淘宝“变形”产品—微淘 操作流程指南 (内测版).
Presentation transcript:

递归下降法 1 递归下降法语法分析原理 递归子程序方法/递归下降法 对每个非终极符按其产生式结构产生相应语法分析子程序。 递归下降法 1 递归下降法语法分析原理 对每个非终极符按其产生式结构产生相应语法分析子程序。 .遇到终极符:执行匹配命令(读入下一token); .遇到非终极符:则执行调用命令; 文法递归相应子程序也递归, 递归子程序方法/递归下降法

例如一条产生式:Stm→while RelExp do Stm 则对应产生式右部的语法分析程序部分如下: begin Match($while); RelExp(); Match($do); Stm(); end

递归下降分析示图 begin Match($while);RelExp;Match($do); Stm end while x > y do if x > y then x := y +x else y := x

2 递归下降法语法分析程序的构造 一、引进下面两个基本动作: ReadToken:从输入流把下一个TOKEN码读到变量token中. Match(a):检查token=a? 若是,则执行ReadToken,否则报错并作相应的处理. 其中a是终极符(TOKEN的语法信息).

递归下降法算法 语法分析主程序:Begin ReadToken; S ; Match(#) end 当产生式形如:A1|2|…|n,则按下面的方法编写子程序A: procedure A( ) begin if tokenPredict(A1) then (1) else if tokenPredict(A2) then (2) else …… if tokenPredict(An) then (n) else err( ) end 其中对i=X1X2…Xn,(i)=’(X1);’(X2);…;’(Xn); 如果XVN,’(X)= X(); 如果XVT,’(X)= Match(X); //即if(token==X)ReadToken(); 如果X= ,() = skip(空语句). 语法分析主程序:Begin ReadToken; S ; Match(#) end

例:假设有文法 Z → a B a B → b B | c Predict(Z→aBa)={a}, Predict(B→bB)={b}, Predict{B→c}={c} 则相应的递归子程序可如下: procedure Z( ) begin if token=a then Match(a);B;Match(a); else err( 1 ) end; (aBa) ’(a); ’( B); ’(a) procedure B ( ) begin if token = b then Match(b); B; else if token = c then Match(c); else err( 2 ) end; 语法分析主程序:Begin ReadToken; Z ; Match(#) End

语法分析主程序:Begin ReadToken; E ; Match(#) end 例: E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ |  F  id | ( E ) Predict( ETE’ ) = first(TE’) = { id , ( } Predict( E’ +TE’ ) = first(+TE’) = { + } Predict( E’  ) = follow(E’) = { ) , # } Predict( T FT’ ) = first(FT’) = { id , ( } Predict( T’ *FT’ ) = first(*FT’) = { * } Predict( T’   ) = follow(T’) = { + , ) , # } Predict( F id ) = first(id) = { id } Predict( F (E) ) = first((E)) = { ( } 语法分析主程序:Begin ReadToken; E ; Match(#) end procedure E( ) begin if token { id , ( } then T; E’ ; else err( 1 ) end;

else if token { ) , # } then skip(); else err( 2 ) end; Predict( ETE’ ) = first(TE’) = { id , ( } Predict( E’ +TE’ ) = first(+TE’) = { + } Predict( E’  ) = follow(E’) = { ) , # } Predict( T FT’ ) = first(FT’) = { id , ( } Predict( T’ *FT’ ) = first(*FT’) = { * } Predict( T’   ) = follow(T’) = { + , ) , # } Predict( F id ) = first(id) = { id } Predict( F (E) ) = first((E)) = { ( } 例: E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ |  F  id | ( E ) procedure E’ ( ) begin if token=“+” then Match($+); T; E’ ; else if token { ) , # } then skip(); else err( 2 ) end;

例: E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ |  F  id | ( E ) Predict( ETE’ ) = first(TE’) = { id , ( } Predict( E’ +TE’ ) = first(+TE’) = { + } Predict( E’  ) = follow(E’) = { ) , # } Predict( T FT’ ) = first(FT’) = { id , ( } Predict( T’ *FT’ ) = first(*FT’) = { * } Predict( T’   ) = follow(T’) = { + , ) , # } Predict( F id ) = first(id) = { id } Predict( F (E) ) = first((E)) = { ( } 例: E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ |  F  id | ( E ) procedure T( ) begin if token { id , ( } then F; T ’ ; else err( 3 ) end;

else if token { +,) , # } then skip (); else err( 4 ) end; Predict( ETE’ ) = first(TE’) = { id , ( } Predict( E’ +TE’ ) = first(+TE’) = { + } Predict( E’  ) = follow(E’) = { ) , # } Predict( T FT’ ) = first(FT’) = { id , ( } Predict( T’ *FT’ ) = first(*FT’) = { * } Predict( T’   ) = follow(T’) = { + , ) , # } Predict( F id ) = first(id) = { id } Predict( F (E) ) = first((E)) = { ( } 例: E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ |  F  id | ( E ) procedure T’ ( ) begin if token=“ * ” then Match($* ); F; T’ ; else if token { +,) , # } then skip (); else err( 4 ) end;

Match( $( ); E; Match( $) ) else err( 5 ) end; Predict( ETE’ ) = first(TE’) = { id , ( } Predict( E’ +TE’ ) = first(+TE’) = { + } Predict( E’  ) = follow(E’) = { ) , # } Predict( T FT’ ) = first(FT’) = { id , ( } Predict( T’ *FT’ ) = first(*FT’) = { * } Predict( T’   ) = follow(T’) = { + , ) , # } Predict( F id ) = first(id) = { id } Predict( F (E) ) = first((E)) = { ( } 例: E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ |  F  id | ( E ) procedure F ( ) begin if token=“ id” then Match($id ) ; else if token=“(” then Match( $( ); E; Match( $) ) else err( 5 ) end;

例:i+i*i # 递归下降分析过程 E→TE’ E’→+TE’│ε T→FT’ T’→*FT’│ε F→(E)│i TE’ E # i + 语法分析主程序:Begin ReadToken; E ; Match(#) end TE’ E # i + + +TE’ T E’ FT’ i + i # M(+) + # + # ε i F T’ ε T FT’ E’ i skip # M(i) skip * * F T’ *FT’ i M(*) M(i) i # # # F T’ ε i M(i) skip

二、递归子程序方法的进一步讨论 产生式A→被选择的条件是: 当前的输入符属于predict(A→). 至多一个产生式被选择的条件是: predict(A→k)  predict(A→j )=,当k  j 递归下降子程序方法的条件: predict(A→k) predict(A→j )=,当k  j

三、对递归下降分析法的评价 递归下降分析法的优点是:简单、直观、程序结构和层次清晰明了,易于手工实现; 递归下降分析法的缺点是:对文法要求高;另一个缺点是频繁的递归调用使得速度慢且占用空间多.