From a computational point of view, the semantic and logical framework provided by rewriting logic has to be complemented with a reflective syntactic framework. Syntactic, or linguistic, reflection allows the effective specification, implementation, and semantic definition of a very wide range of logics and languages--including languages such as Core Maude and Full Maude, whose modules can have user-definable syntax--for which rewriting logic acts as a metalanguage.
The intrinsic characteristics of Maude--mainly, its metalanguage functionality, its reflective nature, and its logical and semantic framework applications--pose very strong requirements on the design of a parsing algorithm for the language, since it has to fulfill the following constraints [52]:
The logical kernel of the current version of the parser is based on the SCP parsing algorithm [54, 53]. SCP is a bidirectional, bottom-up and event-driven parser for unrestricted context-free grammars. From an algorithmic point of view, we have proved the soundness and completeness of SCP. From a computational perspective, SCP avoids overparsing [51], allowing an elegant and very efficient manipulation of a wide set of CFGs. The use of multi-virtual trees [50] at the level of representation and the relations of coverage, partial derivability and adjacency as top-down predictions over the basic bottom-up strategy, obtain a high level of efficiency without diminishing the generality of the algorithm.
The logically proved soundness and completeness of SCP guarantees that the Maude version of SCP (MSCP) will generate all the possible grammatical analyses for each term in a given signature. This avoids some completeness problems detected in the OBJ3 parser.
MSCP is able to analyze beta-extended CFGs (CFGs extended with bubbles and precedence/gathering patterns) [52]. The MSCP parsing algorithm incorporates very sophisticated error detection and error recovery mechanisms based on the notions of partial derivability and adjacency, originally developed in SCP.
Finally, the overall architecture of the MSCP algorithm allows an efficient treatment of syntactic reflection. Besides, this reflective power of the parser supports the parsing and meta-parsing functionality of the META-LEVEL module (Section 2.5) as well as a flexible and natural syntax definition model (see Section 2.7.6).
A detailed description of the SCP Parsing Algorithm may be found in [53]. The notion of overparsing is described in [51], while other internal strategies of SCP such as the use of multi-virtual trees and the formal kernel of the algorithm may be found in [50]. The techniques used in the computational layer of SCP, responsible of the efficiency of the algorithm, are described in [54]. Finally, the technical report [52] describes the Maude version (MSCP) of the parser.