
【計】 unstarred nonterminal
not
【計】 starred nonterminal
在計算機科學與形式語言理論中,"未加星號非終結符"(Non-starred non-terminal symbol)是上下文無關文法(Context-Free Grammar, CFG)中的核心概念。該術語可拆解為以下三個部分進行漢英對照解析:
定義與符號表示
非終結符(Non-terminal symbol)在文法中代表可被替換的語法變量,通常用大寫字母(如S, NP, VP)表示,例如漢英詞典中标注為〈名〉、〈動〉等詞性标籤。未加星號(Non-starred)特指該符號在産生式規則中不攜帶星號(*)運算符,即不包含"零次或多次"的重複語義。
語法結構作用
在巴科斯-諾爾範式(BNF)中,星號用于标記可重複結構(如<word>*
)。未加星號非終結符(如<NounPhrase>
)表明其僅允許單次展開,例如英語句法規則"S → NP VP"中的NP和VP均屬于此類符號,其生成過程具有确定性。
與帶星號符號的對比
相較于帶星號非終結符(如<Adjective>*
允許形容詞短語可選出現),未加星號版本在編譯器設計與自然語言處理中更常用于強制語法成分的精确匹配,例如漢語的"把字句"結構要求必須有賓語成分NP存在。
本術語解釋參考自形式語言理論經典教材《編譯原理》(龍書)及ACM計算機教育文獻庫的核心詞條定義。
“未加星號非終結符”是形式語言和編譯原理中的術語,通常與上下文無關文法(CFG)相關。其含義需從以下兩方面理解:
非終結符
在文法規則中,非終結符是需要被其他符號(終結符或非終結符)替換的符號,代表語言中的抽象結構。例如,在算術表達式文法中,非終結符可能是 <表達式>
或 <項>
。
未加星號
星號(*)表示克林閉包(Kleene star),即允許符號出現零次或多次。若某非終結符未加星號,則說明它在當前規則中隻能嚴格出現一次,不能省略或重複。例如:
A → B* C
表示 B 可重複多次或不存在A → B C
表示 B 必須出現且僅出現一次典型應用場景
在擴展巴科斯範式(EBNF)或正則表達式中,星號用于簡化重複結構的表示。未加星號的非終結符通常用于強制要求某個結構的存在性,例如編程語言中函數定義的參數列表若未加星號,則調用時必須傳入固定數量的參數。
對比示例
假設文法規則為:
<句子> → <主語> <謂語> <賓語>
其中 <主語>
、<謂語>
、<賓語>
均為未加星號非終結符,則每個成分必須嚴格出現一次,不能省略或重複。若改為 <句子> → <主語>* <謂語> <賓語>
,則主語可重複多次(如并列主語)。
【别人正在浏覽】