Context Free Language

Context Free Grammars

Example
- ：
  - 這個集合表示所有形如 “a” 重複 n 次，然後 “b” 重複 n 次的字串。例如，”ab”, “aabb”, “aaabbb” 都屬於這個集合。
  - 儘管看起來簡單，但這個語言不是正規語言。這是一個經典的例子，用來展示有些看起來很簡單的語言，其實並非正規的。
- ：
  - 這個集合表示所有形如 “w” 是一個字串，然後 “w^R” 是 “w” 的逆序的字串。例如，”ababa”，因為它的逆序也是 “ababa”，所以屬於這個集合。類似於上一個例子，這個語言也不是正規語言。
- Regular Languages：
  - 這是一個橢圓形，表示所有正規語言的集合。
- $a^b^$：
  - 這個表示所有由 “a” 和 “b” 組成的字串，其中 “a” 和 “b” 可以重複任意次數（包括 0 次），且 “a” 必須在 “b” 前面。例如，”a”, “bb”, “aabbb” 都屬於這個集合。
- ：
  - 這個表示所有由 “a” 和 “b” 組成的字串，其中 “a” 和 “b” 可以重複任意次數（包括 0 次），且可以任意交錯。例如，”a”, “bb”, “ababab” 都屬於這個集合。
可以如何描述context-free language
- Context-Free Languages: 一種上下文無關的語言
- Context-Free Grammars: 一種能夠生成、描述CFL的文法
- Pushdown Automata: 能夠辨識CFL的自動機，通常是stack

線性文法：
- 在線性文法中，產生規則的形式是每個產生式最多只有一個變量（非終結符號）。例如： A → aB | b
- 這種文法的每個推導步驟中，句法形式只包含一個變量。
非線性文法：
- 在非線性文法中，產生規則可以同時包含多個變量。這使得推導過程中的句法形式可能同時包含多個非終結符號。例如： A → BC | a
- 這樣的推導可以導致包含多個非終結符號的句法形式，如 BC。

用樹來表示 Parser
樹的結構
- 左側標籤（Left Side of Productions）：樹的每個節點標籤為產生式的左側，即非終結符號。例如，如果有一條產生式 S → AB，則樹的根節點 S 代表這個產生式的左側。
- 右側子節點（Right Side Children）：每個節點的子節點對應於其產生式的右側部分。也就是說，節點的子節點表示該非終結符號可以被替換成的符號。例如，對於 S → AB，A 和 B 將作為 S 的子節點。
- 有序樹（Ordered Tree）：一種樹結構，其中每個節點的子節點具有特定的順序。這意味著在樹中的每個節點，其子節點的排列是有意義的，可能影響生成的結果。

成員問題
- Given a string w of terminals, we want to know whether or not w is in L(G) (membership question)
什麼是parsing
- Parsing describes finding a sequence of productions by which a w ϵ L(G) is derived

暴力法 (暴搜)
- top-down pasing
缺點
- Flaws of Exhaustive Search Parsing
  - Tediousness (bad for efficiency)
  - It is possible that it never terminates for strings not in L(G)