正規語言

作品

書籍

課程

程式集

小說集

論文集

散文集

影片集

編輯雜誌

程式人

電子書

JavaScript

計算語言學

微積分

Blender 動畫

C# 語言

系統程式

高等 C 語言

Java

Android

Verilog

Wikidot

R 統計軟體

機率統計

計算機數學

組合語言

人工智慧

開放原始碼

網路資源運用

計算機結構

相關訊息

常用工具

友站連結

在家教育

RSS

最新修改

網頁列表

簡體版

English

語法理論

Syntactic structure (Chromsky)

剖析器

LR parser

遞迴下降剖析法

Recursive Decendent
First(x) = { a <in> Vt | a => *aB} <U> { if a =>* r then {r} else <NIL>
Follow(A) = { a <in> Vt | S =>+ … Aa … } <U> {if S=>+ aA then {r} else <NIL> }
LL(1) Grammer
Predict ( A —> X1…Xm ) =
if r <in> First(X1,…,Xm)
(First(X1,…,Xm) - r) <U> Follow(A)
else
First(X1,…,Xm)
Grammer G is LL(1) <=> Predict(A -> a) <I> Predict(A -> b) = <NIL>
LL(1) Parser
puch(s)
while (! stack_empty())
if ( is_nonterminal(stack_top) and T[stack_top][token] = X -> Y1,…,Ym )
pop(1)
push Ym,Ym-1,…, Y1 onto stack
else if is_terminal(stack_top) and stack_top = token
pop(1)
get_next_token
else
error
LL(1) 的困難有 1. common prefix 2. left recursion

Shift-Reduce 剖析法

Shift - Reduce Parser
s0 s1 … sm | a1 a2 … ai … $
driver ——> output
action table | goto table
Shift-Reduce Driver()
push s0
while true
switch (action[s][T]
case shift :
push(go_to[s][T]
get_next_token(T)
case reduce : (Assume i th production is X->Y1,…,Ym)
pop(m)
push(go_to[s][x])

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License