MRG parser for visual languages

The theory of visual programming languages (VPLs) is very crucial for understanding the visual programming approach. It includes basically formal models for specifying VPLs and the corresponding parsing algorithms. This paper presents a grammatical formalism and an efficient parsing algorithm for visual languages. The proposed formalism, called modified relation grammar (MRG), is a restricted form of the relation grammar (RG). MRG restricts the form of productions and distributes the evaluation rules among various production rules, which makes the grammar more readable. The paper also presents an efficient O(n) parsing algorithm for MRG. The paper includes a number of examples to demonstrate the proposed formalism. It also includes a discussion on the expressive power of the proposed grammar and the correctness of its parsing algorithm. Finally, the paper compares the proposed grammar and its parsing algorithm with a similar restricted form of the RG.