一种从非合流图文法到合流图文法的转换方法

摘要

本发明公开了一种从非合流图文法实例到合流图文法实例的转换方法。该方法包含两个主要步骤：首先判断图文法实例是否合流，如果非合流，则找出所有非合流的产生式对以及相应的导致非合流的产生式合并图的集合；然后依据非合流的产生式合并图在非合流的产生式对中引入变量构造约束将非合流的产生式集合转换成合流的产生式集合。本发明提出的方法将一个隐式上下文相关图文法的非合流图文法实例转换成为合流图文法实例，使受限于合流约束的高效规约算法可以适用于转换后的合流图文法实例，从而大幅度地提高了基于隐式上下文相关图文法的图分析效率，使相应的图文法软件工具具有更强的实用性。