Last Updated ：2025/11/21

context-free grammar

(computing theory) A formal grammar in which every production rule is such that the left-hand side is exactly one non-terminal symbol and the right-hand side is zero or more terminal symbols and/or nonterminal symbols.

Japanese Meaning

形式言語理論における文脈自由文法は、各生成規則の左辺が単一の非終端記号のみで、右辺が任意の数の終端記号および非終端記号からなる文法体系です。

What is this buttons?

A context-free grammar can generate languages that are not regular yet can still be parsed efficiently.

Google Translation / DeepL Translation

左辺がちょうど1つの非終端記号で右辺が0個以上の終端記号からなる形式文法（文脈自由文法）は、正規言語ではないがそれでも効率的に構文解析できる言語を生成し得る。

Details

Sense（1）

It remains to explain one final concept, namely what a context free language is. (Don’t get confused: we’ve told you what a context free grammar is, but not what a context free language is.) Quite simply, a context free language is a language that can be generated by a context free grammar. Some languages are context free, and some are not. For example, it seems plausible that English is a context free language. That is, it is probably possible to write a context free grammar that generates all (and only) the sentences that native speakers find acceptable. On the other hand, some dialects of Swiss-German are not context free. It can be proved mathematically that no context free grammar can generate all (and only) the sentences that native speakers of Swiss-German find acceptable.¹ So if you wanted to write a grammar for such dialects, you would have to employ additional grammatical mechanisms, not merely context free rules.

Google Translation / DeepL Translation