作者flydragon198 (Richard)
看板Examination
標題Re: [考題] 99年高考三級 程式設計 第四題
時間Mon Jun 9 01:30:35 2014
※ 引述《Burgerking24 (喜歡漢堡王)》之銘言:
: <E> --> <T> | <E> * <T>
: <T> --> <V> | <V> + <T>
: <V> --> a
: 請問這段文法如何轉換成右側文法
: google很久都沒找到看得懂的答案
: 可以請有看懂的高手指點一下嗎
: 謝謝!!
<E> --> <T> |
<E> * <T> 這個是左遞迴,因為<E> 在左邊
到時候如果展開,黃色的<E> 部分會變成<T>,或者<E>*<T>
這樣的話,展開時,左邊的記憶體空間需要越來越大,所以必須要改成右遞迴
<E> --> <T> | <T> * <E> 把 <E>放到右邊就變右遞迴了,真是簡單XD
但是這樣的話, <T> 都在左邊,這樣好像是違反左因子
所以還要再修改讓 <E> --> <T> | <T> * <E> 變成
<E> --> <T><E'>
<E'> --> *<T><E'> | ε
不過這裡我是直接背上面這個轉換的樣版就是了,書上好像都沒寫轉換推導過程
http://dl.ibrain.com.tw/Paper/KP/431.pdf
--
我們一路奮戰所作的一切,不是為了改變世界,而是為了不讓世界改變我們----熔爐
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.47.132.127
※ 文章網址: http://www.ptt.cc/bbs/Examination/M.1402248640.A.21A.html
※ 編輯: flydragon198 (114.47.132.127), 06/09/2014 01:32:39
推 freshcute:把樹畫出來就可以推導了! 06/09 02:14
推 bloodyaugust:這題目寫 right linear(右側遞迴)是不是有點問題? 06/09 09:28
→ bloodyaugust:right linear和右遞迴好像是不同的東西 06/09 09:28
→ silentlich:我花了一個小時在想這東西為什麼會是linear...... 06/09 17:23