什么是上下文无关语法? [英] What is a Context Free Grammar?
问题描述
有人可以向我解释什么是上下文无关的语法吗?在查看了Wikipedia条目,然后查看了有关正式语法的Wikipedia条目之后,我完全被迷住了.有人会乐于解释这些东西是什么吗?
Can someone explain to me what a context free grammar is? After looking at the Wikipedia entry and then the Wikipedia entry on formal grammar, I am left utterly and totally befuddled. Would someone be so kind as to explain what these things are?
我想知道这是因为我希望研究解析以及正则表达式引擎的局限性.
I am wondering this because I wish to investigate parsing, and also on the side, the limitation of a regex engine.
我不确定这些术语是否与编程直接相关,或者它们是否与语言学总体上更相关.我很抱歉,如果可以的话,也许可以动议吗?
I'm not sure if these terms are directly programming related, or if they are related more to linguistics in general. If that is the case, I apologize, perhaps this could be moved if so?
推荐答案
上下文无关文法是一种满足某些属性的文法.在计算机科学中,语法描述语言.具体来说,它们描述形式语言.
A context free grammar is a grammar which satisfies certain properties. In computer science, grammars describe languages; specifically, they describe formal languages.
形式语言只是一组字符串(符号序列……与单词"string"的编程用法非常相似)的集合(一组对象的数学术语).形式语言的一个简单示例是长度为三的所有二进制字符串的集合,{000、001、010、011、100、101、110、111}.
A formal language is just a set (mathematical term for a collection of objects) of strings (sequences of symbols... very similar to the programming usage of the word "string"). A simple example of a formal language is the set of all binary strings of length three, {000, 001, 010, 011, 100, 101, 110, 111}.
语法通过定义可以用语法描述的语言构造字符串的转换来工作.语法将说明如何将起始符号(通常为S)转换为某些符号字符串.之前给出的语言的语法是:
Grammars work by defining transformations you can make to construct a string in the language described by a grammar. Grammars will say how to transform a start symbol (usually S) into some string of symbols. A grammar for the language given before is:
S -> BBB
B -> 0
B -> 1
这种解释的方式是说S
可以用BBB
替换,而B
可以用0替换,而B
可以用1替换.因此构造字符串010,我们可以做S -> BBB -> 0BB -> 01B -> 010
.
The way to interpret this is to say that S
can be replaced by BBB
, and B
can be replaced by 0, and B
can be replaced by 1. So to construct the string 010 we can do S -> BBB -> 0BB -> 01B -> 010
.
无上下文语法只是一种语法,其中您要替换的内容(箭头的左侧)是单个非终结符"符号.非终结符是您在语法中使用的,不会出现在最终字符串中的任何符号.在上面的语法中,"S"和"B"是非终结符号,而"0"和"1"是终结"符号.像
A context-free grammar is simply a grammar where the thing that you're replacing (left of the arrow) is a single "non-terminal" symbol. A non-terminal symbol is any symbol you use in the grammar that can't appear in your final strings. In the grammar above, "S" and "B" are non-terminal symbols, and "0" and "1" are "terminal" symbols. Grammars like
S -> AB
AB -> 1
A -> AA
B -> 0
由于包含诸如"AB-> 1"之类的规则,因此不规则.
Are not regular since they contain rules like "AB -> 1".
这篇关于什么是上下文无关语法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!