Algorithms for transforming context-free grammars into L-graphs

Abstract

Formal language theory holds a significant place in computer science, where context-free grammars, due to their powerful expressiveness, are widely applied in areas such as programming language design, natural language processing, and compiler construction. Traditionally, pushdown automata have been the primary tool for recognizing and processing context-free languages. However, the fragmentation of state transition descriptions and stack operations into separate commands complicates the analysis of computations, hindering practical application. L-graphs are conceived as a more advanced and compact tool for representing and analyzing formal languages, thanks to their intuitive graphical structure and the clear semantics of graph paths that reflect computations. This paper presents a systematic transformation algorithm capable of converting an arbitrary context-free grammar into an equivalent context-free L-graph. This method performs an intuitive, one-to-one conversion of grammatical structures into graphical ones. Unlike pushdown automata, L-graphs do not involve explicit stack operations, instead using bracket labels to implement recursive structures, which makes their usage more intuitive. Furthermore, the study demonstrates the feasibility of efficient syntactic parsing using L-graphs, highlighting their practical value. While retaining the expressive power of contextfree grammars, L-graphs are more amenable to optimization (such as eliminating redundant vertices and arcs, reducing cyclic complexity, etc.), enhancing their effectiveness for both theoretical research and practical applications.