有人可以给出一个简单但非玩具的上下文敏感语法示例吗？

Question

我正在尝试理解上下文敏感的语法,我理解为什么语言会像

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

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

Answer 1

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

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

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

在自然语言处理(NLP)中也使用上下文敏感语法.大多数自然语言都是上下文敏感语言的例子.(我不确定梵语).

我将尝试用一个愚蠢而简单的例子解释它(这只是一个想法,你可以改进它):

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

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

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

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

但

             Grijesh    am       working       [wrong statement]

原因:<TENSE>的值取决于值<NOUN>(例如I <TENSE> --> I am),因此语法不会生成正确的英语语句.

实际上我们不能为完整的英语写一个无上下文的语法!

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

参考:您可以观看Arun Kumar博士的讲座. _{在一些讲座中,他准确地解释了你感兴趣的内容.}