November 2017
Beginner to intermediate
344 pages
7h 2m
Chinese
Content preview from 深入理解運算原理｜從簡單的機器到無所不能的程式
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
130
|
第 4 章
嗯，沒有，事實證明，並沒有。只有 NFA 轉成 DFA 的訣技能夠運作，是因為我們可以
使用單一的 DFA 狀態來表示諸多可能的 NFA 狀態。為了模擬 NFA，我們只需要記錄
目前它所處的狀態為何，然後在每次讀取輸入的字元時，挑選一組不同的可能狀態，且
若我們給它正確的規則，DFA 很容易就能完成這件工作。
但這項訣技對 PDA 無效：我們無法有效的將多個 NPDA 組態表示成單一的 DPDA 組
態。這個問題不出所料的就是堆疊。NPDA 模擬物需要知道目前可以位在堆疊頂端的所
有字元，而且它必須能同時提出和推入多個模擬的堆疊。因為無法將所有可能的堆疊合
併成單一個堆疊，以致於 DPDA 仍然可以看到所有最頂端的字元，並個別存取每個可
能的堆疊。雖然編寫 Ruby 程式來完成這所有的一切並沒有任何困難，只是 DPDA 沒有
足夠的能力處理這些。
因此，不幸的是，我們 NPDA 模擬物的行為並不像 DPDA，而且
沒有
NPDA 轉成
DPDA 的演算法。未標記的回文問題就是個例子，NPDA 可以做一些 DPDA 做不到的
事情，因此非決定論下推自動機
確實
比決定論的版本擁有更多能力。
利用下推自動機解析
第 84 頁的『正規運算式』討論過如何使用非決定論有限自動機來實作正規運算式匹
配。下推自動機也有一項重要的實際應用：它們可以用來解析程式設計語言。
我們已經在第 61 頁的『實作解析器』看到如何使用 Treetop 替部分的 SIMPLE 語言建
置解析器。Treetop 解析器使用單一的 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.