SAGA -- Syntax Analyzer Generator for Agents

LALR(1) parser generators in conjunction with imperative programming languages is the standard solution for parsing applications. Contrary to popular belief, this situation is not entirely satisfactory. With imperative tools like Yacc, it is difficult to add actions to a grammar without introducing conflicts. Also, LALR(1) is not powerful enough to meet the needs of languages like C++. We argue that LALR(1) parsing in conjuction with concurrent constraint programming is an interesting option that solves the former problem. We also show how deep guards and don't-know non-determinism can be exploited to solve the latter problem. These ideas have been incorporated in the Saga parser generator described in this report. Saga is an integrated generator for lexical analyzers and parsers. It is based on AKL, a multiparadigm programming language based on a concurrent constraint framework. It is intended both as a research tool to demonstrate the power offered by concurrent constraints, and as a practical tool for the Agents programming system. As a practical tool, Saga features many improvements over tools like Yacc. For example, Saga offers powerful syntax, elegant reporting and resolution of conflicts and powerful error handling in the generated syntax analyzers