有人可以给出一个简单但不是玩具的上下文相关语法示例吗? [英] Can someone give a simple but non-toy example of a context-sensitive grammar?

问题描述

我正在尝试理解上下文相关的语法，并且理解为什么这样的语言

I'm trying to understand context-sensitive grammars, and I understand why languages like

1. {ww | w是一个字符串}
2. {a ⁿ b ⁿ c ⁿ | a，b，c是符号}

1. {ww | w is a string}
2. {aⁿ bⁿ cⁿ | a,b,c are symbols}

不是上下文无关的，但是我想知道一种类似于未类型化lambda演算的语言是否对上下文敏感.我想看一个简单但非玩具的示例(我考虑了上面的玩具示例)，它是上下文相关语法的示例，对于某些生产规则，例如可以判断是否有一些符号字符串当前处于范围内(例如，在生成函数主体时).上下文敏感的语法是否足够强大，足以使未定义/未声明/未绑定的变量成为语法错误(而非语义错误)?

are not context free, but what I'd like to know if a language similar to the untyped lambda calculus is context sensitive. I'd like to see an example of a simple, but non-toy (I consider the above toy examples), example of a context-sensitive grammar that can, for some production rule, e.g., tell whether or not some string of symbols is in scope currently (e.g. when producing the body of a function). Are context sensitive grammars powerful enough to make undefined/undeclared/unbound variables a syntactic (rather than semantic) error?

推荐答案

是的，上下文敏感语法(CSG)的功能足以检查未定义/未声明/未绑定的变量，但不幸的是，我们不知道任何有效的算法解析CSG字符串.

Yes, context-sensitive grammars (CSG) are powerful enough to make undefined/undeclared/unbound variables check, but unfortunately we don't know any efficient algorithm to parse strings of CSG.

上下文相关语言的一个真实示例是C编程语言.先声明变量然后再使用它们的功能使C语言成为上下文敏感语言(CSL). (我不知道无类型的lambda演算.)

A real example of a context-sensitive language is the C programming language. A feature like declare variables first and then use them later make C-language a context-sensitive language (CSL). (I don't know about untyped lambda calculus).

并且因为我们不知道CSL(或CSG)的任何线性解析算法.这就是在编译器设计中的原因，因为我们知道有效的算法来解析CFG(如果格式受限)，所以我们使用CFG(及其解析算法)进行语法检查.编译器首先解析上下文无关的功能，然后以有问题的方式处理上下文相关的功能(例如，检查符号表中是否使用了任何已定义的变量，否则将产生错误).

And because we don't know any linear parsing algorithm for CSL (or CSG). That is the reason in compiler design, we use CFG (and its parsing algoritm only) for syntax checking since we know efficient algorithms to parse CFG (if it's in restricted form). Compilers first parse a context free feature and then later handle context-sensitive features in a problematically way (for example, checks any used variable in the symbol table if it's defined. Otherwise, it generates an error).

自然语言处理(NLP)中也使用了上下文相关的语法.而且大多数自然语言都是上下文相关语言的示例. (我不确定梵语语言).

Also context-sensitive grammar is used in natural-language processing (NLP). And most natural languages are examples of context-sensitive languages. (I am not sure for the Sanskrit language).

我将尝试通过傻但简单的示例来解释它(这只是一个主意，您可以对其进行细化):

I will try to explain it with a silly but simple example (it's just an idea, you can refine it):

NOUN     -->  { BlueBomber, Grijesh, I, We}
TENSE    -->  { am, was, is, were}
VERB     -->  { going, eating, working}

SENTENCE --> <NOUN> <TENSE> <VERB>

现在，使用此语法，我们可以生成一些正确的语句，但是有些语句也是错误的.例如，

Now, using this grammar, we can generate some correct statements, but some are wrong too. For example,

SENTENCE --> <NOUN>   <TENSE>   <VERB>
             Grijesh    is       working       [Correct statement]

但是

             Grijesh    am       working       [wrong statement]

原因:< TENSE>的值取决于< NOUN>的值(例如，I <TENSE> --> I am)，因此语法不能以英语生成正确的陈述.

Reason: the value of <TENSE> depends on value <NOUN> (for example, I <TENSE> --> I am) and hence the grammar doesn't generate correct statements in the English language.

实际上，我们不能为完整的英语编写无上下文语法！

Actually we can't write a context-free grammar for complete English!

_{您可能已经注意到，任何自然语言翻译器或语法检查器均无法正常工作(尝试使用长语句).因为此问题属于上下文敏感的解析算法.}

参考:您可以观看博士.阿伦·库玛(Arun Kumar)的演讲. _{在一些演讲中，他准确地解释了您感兴趣的内容.}

这篇关于有人可以给出一个简单但不是玩具的上下文相关语法示例吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！