Precedence-regular grammars

Abstract

A new class of grammars (precedence-regular grammars) is obtained as a proper extension of the class of weak precedence grammars. A parsing algorithm is described for this class of grammars, using Domolki's algorithm. Finally a criterion is obtained to decide whether a given context-free grammar belongs to this class.

Keywords:

• Context-free grammar
• finite transducer mapping
• precedence grammar
• regular partition
• weak precedence relations

C.R. Categories:

• 5.22
• 5.23
• 5.24

Department of Mathematics, Eindhovcn University of Technology,Eindhoven, The Netherlands.

Department of Mathematics, Eindhovcn University of Technology,Eindhoven, The Netherlands.

Notes

Department of Mathematics, Eindhovcn University of Technology,Eindhoven, The Netherlands.