申論題 - 阿摩線上測驗

申論題資訊

試卷：104年 - 104 公務升官等考試_薦任_資訊處理：程式語言#41168
科目：程式語言
年份：104年
排序：0

申論題內容

一、電腦程式語言中，有一種名為 context free language，請問其性質為何？並舉例說明。（15 分）

詳解 (共 2 筆)

詳解提供者：114年高考上榜

在電腦程式語言中，context-free language (無環語言) 是一種符合文法 (grammar) 規則的語言，其特點是每個規則只與符號自身有關，而不受上下文的影響。

簡單來說，context-free language 就是一種語言，其文法可以用上下文無關文法 (context-free grammar) 描述。而 context-free grammar 是指由一個開始符號 (start symbol) 開始，每個規則都只涉及單一非終端符號 (nonterminal symbol) 的產生式 (production)，而這些產生式不會受到上下文的影響。

一個經典的例子是平衡括號語言。這是一個由左右括號組成的語言，其中每個左括號都必須有一個對應的右括號。這個語言可以用下面的 context-free grammar 描述：

S -> (S)S

S -> ε

其中，S 是起始符號，ε 代表空字串。這個文法的意思是，一個平衡括號語言可以由一對左右括號和另一個平衡括號語言組成，或者是一個空字串。

例如，這個文法可以生成以下合法的平衡括號序列：

()

(())

()()

((()))

()()()

這些序列都可以用相同的文法推導出來，而且都是 context-free language 的範例。

詳解提供者：hchungw

上下文無關語言是計算機科學中重要的一類語言，特別是在語言設計和編譯器構建中廣泛使用。其主要性質包括由上下文無關文法定義、規則應用不依賴上下文、可以解析和封閉性等。通過這些特性，我們可以設計和分析許多語言和結構，如編程語言的語法、平衡括號和算術表達式等。

1. 平衡括號語言

語言描述：包含平衡括號的所有字串。文法：

rust

複製程式碼

G1 = ( {S}, {'(', ')'}, {S -> SS | (S) | ε}, S )

這個文法生成的語言包括：ε、()、(())、()()、((())) 等等。

2. 形如 anbna^n b^nanbn 的語言

語言描述：所有形式為 anbna^n b^nanbn 的字串，其中 n≥0n \geq 0n≥0。文法：

rust

複製程式碼

G2 = ( {S}, {'a', 'b'}, {S -> aSb | ε}, S )

這個文法生成的語言包括：ε、ab、aabb、aaabbb 等等。

3. 簡單算術表達式

語言描述：由加法和乘法組成的簡單算術表達式。文法：

r

複製程式碼

G3 = ( {E, T, F}, {'+', '*', '(', ')', 'a'}, {E -> E+T | T, T -> T*F | F, F -> (E) | a}, E )