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

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

基本信息

批准号：
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)の長さからなる文字列全体を表す言語を記述できるという結果を新たに得た。

由于去年推出的带有lookahead的上下文无关语法的语义，存在无法执行基本语法转换操作赋值的反向操作的情况，并且存在关于转换为标准形式和数量的讨论识别算法所需的计算量很大，但问题是很难分析。今年，我们得到了一个使用三元语义的公式来作为解决这个问题的方法。这考虑了一种三元前瞻语言，它是从一组字符串到 true、false 和 undefined 的映射，在它们之间放置一个最小化 undefined 的顺序，并在该顺序下找到最小解决方案，这意味着思考。这种方法是程序表示语义中的标准方法，在逻辑编程中称为Fitting语义。事实证明，三元语义允许我们处理所有语法并自由地执行与赋值相反的操作。即使在这种新的语义下，它也是上下文无关语法和分析表示语法的扩展，并且关于闭包和可判定性、排除补语闭包和表达能力等基本属性的结果已经被证明是有效的。接下来，针对前瞻上下文无关文法的识别算法，我们提出了一种基于微分的识别算法，并分析了其计算复杂度。因此，该算法的时间复杂度为 O(n^3 |G|)，空间复杂度为 O(n^2 |G|)。这与上下文无关文法得到的结果相同，但由于前瞻性质的差异，证明略有不同，并且由于性质的差异，Valiant方法，即矩阵乘法的计算复杂度为可见这不能应用于上下文无关语法。最后，在表达能力方面，我们找到了一种在具有前瞻功能的上下文无关语法中模仿 k 区间递推公式的方法，并且可以编写一种语言来表示多项式 p 的整个长度为 p(n) 的字符串。取得了新的成果。