李玉萍

（商丘师范学院 计算机与信息技术学院，河南 商丘 476000）

基于单向点格自动机的UPG文法识别并行算法

李玉萍

（商丘师范学院 计算机与信息技术学院，河南 商丘 476000）

UPG文法是一种特殊的生成文法，在分析的过程中可以没有回溯。该文法能够更好地描述自然语言中特殊的语法结构。单向点格自动机是进行语言并行识别的模型。通过对该文法和点格自动机深入的分析，提出了一种在并行环境下基于点格自动机的无回溯的语法分析和识别算法。文章通过实例详细描述了算法并行处理的过程，验证算法的正确性和可行性。

UPD文法；单向点格自动机；语法分析

点格自动机是一种数学模型，由J.von Neumann在40年代提出，最初用它来模拟生物系统中某些自组织现象。随着计算机技术的发展，它已成为分析复杂现象的一种有效工具。

目前，大多数程序设计语言采用上下文无关文法进行描述，但上下无关文法描述问题的能力有限，因此对上下文无关文法进行扩充，形成了一种特殊的UPG文法。UPG文法作为一种特殊的生成文法，具有重要特性，在进行语法分析的时可以没有回溯，能够更好地描述自然语言中特定的语法结构。

随着计算机的发展趋向于并行化，多处理机并行处理是不可逆转的时代，因此对UPD文法在并行环境下处理过程的分析和研究有其理论和实践意义。根据点格自动机和UPD文法的特殊的属性，文章提出了利用单向点格自动机模型对UPD文法进行并行转换和并行语言识别的算法，通过实例进行分析，说明了算法的正确性和可行性。……