论文标题
使用连词和布尔语法描述编程语言的语法
Describing the syntax of programming languages using conjunctive and Boolean grammars
论文作者
论文摘要
弗洛伊德（Floyd）的经典结果（“关于阿尔戈尔60的短语结构语法的不存在，1962年）指出，任何明智的编程语言的完整语法都不能由普通种类的形式语法（乔姆斯基的````````````````````''）））了。本文使用与连词和否定操作员（称为连词语法和布尔语法）扩展的语法，用简单的无类型程序编程语言描述了一组完善的程序。完整的布尔语法在使用之前定义了诸如变量和函数声明之类的概念，并进行了解释。使用布尔语法的广义LR解析算法，然后可以在其长度$ o（n^4）$中解析程序，而另一种已知的算法则允许亚基时时间解析。接下来，显示如何将这种语法转换为明确的结合语法，并进行平方分析。这显然成为完全通过计算可行的形式语法的编程语言语法的第一个规范。
A classical result by Floyd ("On the non-existence of a phrase structure grammar for ALGOL 60", 1962) states that the complete syntax of any sensible programming language cannot be described by the ordinary kind of formal grammars (Chomsky's ``context-free''). This paper uses grammars extended with conjunction and negation operators, known as conjunctive grammars and Boolean grammars, to describe the set of well-formed programs in a simple typeless procedural programming language. A complete Boolean grammar, which defines such concepts as declaration of variables and functions before their use, is constructed and explained. Using the Generalized LR parsing algorithm for Boolean grammars, a program can then be parsed in time $O(n^4)$ in its length, while another known algorithm allows subcubic-time parsing. Next, it is shown how to transform this grammar to an unambiguous conjunctive grammar, with square-time parsing. This becomes apparently the first specification of the syntax of a programming language entirely by a computationally feasible formal grammar.
