実用的な構文解析技術と形式言語理論をつなぐ統一的な理論基盤の構築

建立连接实用句法分析技术和形式语言理论的统一理论基础

基本信息

批准号：
20J23184
负责人：
宮嵜貴之
金额：
$ 1.6万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-24 至 2023-03-31
项目状态：
已结题

项目摘要

昨年度に導入した先読み付き文脈自由文法の意味論には、基本的な文法の変換操作である代入の逆の操作が行えない場合があり、標準形への変換についての議論や認識アルゴリズムの計算量の解析が困難であるという問題があった。本年度はその問題を解決する手法として3値の意味論を用いた定式化を得た。これは、文字列の組から真、偽、未定義への写像である3値の先読み付き言語を考え、それらの間に未定義を最小とする順序を入れ、その順序の下での最小解を考えるというものである。この方法は、プログラムの表示的意味論において標準的な方法であり、論理プログラミングにおいてはFittingの意味論と呼ばれている。3値の意味論によって、全ての文法を扱うことができ、代入の逆の操作を自由に行うことができることが分かった。この新たな意味論の下でも、文脈自由文法と解析表現文法の両者の拡張となること、補集合の閉包性を除く閉包性や決定可能性などの基本的な性質、表現力についての結果が成り立つことを証明した。次に、先読み付き文脈自由文法の認識アルゴリズムに関して、微分による認識アルゴリズムを与え、その計算量の解析を行った。その結果として、そのアルゴリズムは、入力文字列の長さn、先読み付き文脈自由文法の大きさ|G|に対し、時間計算量O(n^3 |G|)、空間計算量O(n^2 |G|)で計算可能であることが分かった。これは文脈自由文法に対して得られている結果と同じであるが、先読みの持つ性質の違いによって証明は少し異なり、また、その性質の違いから行列乗算の計算量であるValiant法は先読み付き文脈自由文法に適用することができないことがわかる。最後に、表現力に関して、先読み付き文脈自由文法でk項間漸化式を模倣する方法を発見し、多項式pに対してp(n)の長さからなる文字列全体を表す言語を記述できるという結果を新たに得た。

去年引入的无上文的语法的语义是一个问题，即不能进行基本语法转换操作的分配的反作用，并且很难就识别算法的计算复杂性进行转换为标准形式和分析的讨论。今年，我们使用三值语义作为解决此问题的方法获得了公式。这涉及考虑三个值的读取语言，该语言是将字符串的映射设置为真实，错误和未定义的，在其之间下订单，以最低的未定义，并考虑该顺序下的最低解决方案。该方法是程序化表示语义的标准方法，被称为逻辑编程中的拟合语义。已经发现，三元语义允许处理所有语法，并且可以自由执行分配的反向操作。事实证明，即使在这种新的语义理论下，它也是无上下文语法和分析表达语法的扩展，以及基本特性（例如闭合和确定性）的结果，不包括互补集的封闭以及表达性的关闭，也是正确的。接下来，关于预读无上下文语法的识别算法，给出了差异识别算法，并分析了计算复杂性。结果，发现算法可以用时间复杂性O（n^3 | g |）和空间复杂性O（n^2 | g |）对于输入字符串的长度以及预遵循的无上下文语法| g |的大小来计算。这与无上下文语法获得的结果相同，但是根据预读的性质，证明略有不同，并且与属性的差异相同，很明显，Valiant方法（即矩阵乘法的计算复杂性）不能将其应用于无上下文的语法上的无上下文读取。最后，就表现力而言，我们发现了一种模仿K-Term Recisrence表达式的方法，并使用预读的无上下文语法，并新获得的结果我们可以编写一种语言，该语言代表多项式p的整个p（n）长度。