Scanning and Parsing Languages with Ambiguities and Constraints: The Lamb and Fence Algorithms Luis Quesada, Fernando Berzal, and Francisco J. Cortijo Department of Computer Science and Artificial Intelligence, 5 1 CITIC, University of Granada, 0 Granada 18071, Spain 2 {lquesada, fberzal, cb}@decsai.ugr.es n a J 1 1 Abstract ] L Traditional language processing tools constrain language designers to specific kinds of gram- F mars. Incontrast,model-basedlanguageprocessingtoolsdecouplelanguagedesignfromlanguage . s processing. Thesetoolsallowtheoccurrenceoflexicalandsyntacticambiguitiesinlanguagespec- c ifications and the declarative specification of constraints for resolving them. As a result, these [ techniquesrequirescannersandparsersabletoparsecontext-freegrammars,handle ambiguities, 1 and enforce constraints for disambiguation. In this paper, we present Lamb and Fence. Lamb is v a scanning algorithm that supports ambiguous token definitions and the specification of custom 5 pattern matchers and constraints. Fence is a chart parsing algorithm that supports ambiguous 9 7 context-free grammars and the definition of constraints on associativity, composition, and prece- 2 dence,aswellascustomconstraints. LambandFence,inconjunction,enabletheimplementation 0 of the ModelCC model-based language processing tool. . 1 Keywords: Scanners, parsers, context-free grammars,ambiguities, constraints. 0 5 1 1. Introduction : v i Traditionallanguageprocessingtools[3]requirethetextualspecificationofthelanguagegrammar X in order to produce scanners and parsers for the desired language. r a Incontrast,model-basedlanguageprocessingtools[22]automaticallygenerateagrammarfor the desired language (as well as the corresponding scanners and parsers for the language) given a conceptual model of the language. Model-based language processing tools encourage model reuse and combination in order to reduce developer workload. The combination of separate parts of different models could yield language ambiguities. For example, a model considers, among other language elements, integers andpoints,andanothermodelconsiders,amongotherelements, decimals;whencombiningparts of both models into another model, the “5.2” string could be interpreted either as a sequence of integer point integer tokens, or as a single decimal token. Eventhespecificationofasinglemodelthatconsidersbothinteger,point,anddecimal tokens is more elegant when ambiguities are allowed, since the ambiguity does not have to be minded or worked around. It should be noted that the typical workaround, that is, specifying that the decimal symboliscompositionoftwointeger symbolsseparatedbyapoint symbol,issemantically incorrect, since a decimal does not consist of two integers. Lexical ambiguities occur when an input string simultaneously corresponds to several token sequences [31], in which tokens may overlap. Syntactic ambiguities occur when a tokensequence can be parsed into several parse trees [1]. Therefore,model-basedlanguageprocessingtoolsrequireambiguitysupportinboththescan- ner and the parser (or just in the parser, if we dispense with the lexical analyzer in scannerless parsing). Thelanguagemodelgeneratedbyamodel-basedparsergeneratormaycontainepsilonproduc- tions (e.g. A := ǫ), recursive productions (e.g. A := Ab), grammar cycles (e.g. A := c, A := B, and B := A), constraints on associativities, compositions, and precedences, as well as custom constraints. Therefore, a parsing algorithm that supports these constructions and constraints is required. In this paper, we describe such a parsing algorithm, Fence, and its accompanying scanning algorithm, Lamb, in detail. Lamb [39] is a scanning algorithm that captures all the possible sequences of tokens within a given input string and produces a lexical analysis graph that describes them all. Fence [40]is bottom-upchartparsingalgorithmthat accepts lexicalanalysisgraphsas input, performs an efficient syntactic analysisof them by taking constraints into account, and produces parse graphs that represent all the valid parse trees. The Fence parsing algorithm complements the Lamb scanning algorithm by performing an implicit context-sensitive analysis of the lexical analysis graphprovidedby Lamb, as the parsing process determines which token sequences are valid in the parse graph and discards incorrect token sequences. In addition, Fence supports every possible construction in a context-free language grammar, including epsilon productions and recursive productions. Both Lamb and Fence are part of the ModelCC model-based parser generator [41, 42, 38], a powerful tool that demonstrates the feasibility of the model-driven approach we advocate. The ModelCC suite is open-source and it can be downloaded from http://www.modelcc.org. The organization of this paper is as follows. Section 2 describes formal grammars, surveys scanning and parsing algorithms, reviews scanner and parser generators, and introduces the model-driven language specification approach. Section 3 presents the Lamb scanning algorithm, whereas Section 4 presents the Fence parsing algorithm. Finally, Section 5 summarizes our conclusions and provides some pointers for further research. 2. Background Inthissection,weintroducecontext-freegrammars(Subsection2.1),describethetypicalarchitec- tureoflanguageprocessorfront-ends(Subsection2.2),surveykeyparsingalgorithms(Subsection 2.3), review existing scanner and parser generators (Subsection 2.4), and introduce model-based language specification techniques and the ModelCC model-based parser generator (Subsection 2.5). 2 2.1. Context-Free Grammars Context-free grammars are used to specify the syntax of context-free languages [2]. Using a set of rules, a context-free grammar describes how to form strings from the language alphabet that are valid according to the language syntax. A context-free grammar G is formally defined [5] as the tuple (N,Σ,P,S), where: • N is the finite set of nonterminal symbols of the language, sometimes called syntactic variables, none of which appear in the language strings. • Σ is the finite set of terminal symbols of the language, also called tokens, which constitute the language alphabet (i.e. they appear in the language strings). Therefore, Σ is disjoint from N. • P is a finite set of productions, each one of the form N →(Σ∪N)∗, where ∗ is the Kleene star operator, ∪ denotes set union, the part before the arrow is called the LHS (left-hand side) of the production, and the part after the arrowis called the RHS (right-handside) of the production. • S is a distinguished nonterminal symbol, S ∈N: the grammar start symbol. Forconvenience,whenseveralproductionssharetheirleft-handside,theycanbegroupedinto a single production containing their the shared left-hand side and all their different right-hand sides separated by |. A context-free grammar is said to be ambiguous if there exists at least one string that can be generated by the grammar in more than one way. In fact, some context-free languages are inherently ambiguous (i.e. all context-free grammars generating them are ambiguous). 2.2. The Architecture of Language Processors Thearchitectureofalanguage-processingsystemdecomposeslanguageprocessingintoseveral steps which are typically grouped into two phases: analysis and synthesis. The analysis phase, which is responsibility of the language processor front end, starts by breaking up its input into its constituent pieces (lexical analysis or scanning) and imposing a grammatical structure upon them (syntax analysis or parsing). The language processor back end will later synthesize the desired target from the results provided by the front end. A lexical analyzer, also called lexer or scanner, processes an input string conforming to a language specification and produces the tokens found within it. Lexical ambiguities occur when a given input string simultaneously corresponds to several token sequences [31], in which tokens may overlap. A parser, also called syntactic analyzer, processes sequences of input tokens and determines their grammatical structure with respect to the given language grammar, usually in the form of parse trees. In the absence of lexical ambiguities, the parser input consists of a stream of tokens,whereasitwillbe adirectedacyclicgraphoftokens whenlexicalambiguitiesare present. Syntactic ambiguities occur when a given set of tokens simultaneously corresponds to several valid parse trees [1]. 3 2.3. Scanning and Parsing Algorithms Scanning and parsing algorithms are characterized by the expression power of the languages to which they can be applied, their support for ambiguities or lack thereof, and the constraints they impose on language specifications. Traditional lexical analyzers are based on a finite-state machine that is built from a set of regularexpressions[29],eachofwhichdescribesatokentype. Theefficiencyofregularexpression lexical analyzers is O(n), being n the input string length. Efficientparsersforcertainclassesofcontext-freegrammarsexist. Theseincludetop-downLL parsers, which construct a leftmost derivation of the input sentence, and bottom-up LR parsers, which construct a rightmost derivation of the input sentence. LL grammars were formally introduced in [27], albeit LL(k) parsers predate their name [34]. An LL parser is called an LL(k) parser if it uses k lookahead tokens when parsing a sentence, while it is an LL(*) parser if it is not restricted to a finite set of k lookahead tokens and it can make parsing decisions by recognizing whether the following tokens belong to a regular language [18, 32], or by using syntactic orsemantic predicates [36]. While LL(k) parsersare alwayslinear, LL(*) ranges from O(n) to O(n2). LR parsers were introduced by Knuth [23]. DeRemer later developed the LALR [7, 9] and SLR [8] parsers that are in use today. When parsing theory was originally developed, machine resources were scarce, and so parser efficiency was the paramount concern [35]. Hence all the aforementioned parsing algorithms parse in linear time (i.e. their efficiency is O(n), being n the input string length) and they do not support syntactic ambiguities. Efficient LR and LL parsers for certain classes of ambiguous grammars are also possible by using simple disambiguating rules [1, 11]. A general-purpose dynamic programming algorithm for parsing context-free grammars was independently developed by Cocke [6], Younger [49], and Kasami [20]: the CYK parser. This general-purposealgorithmisO(n3)forambiguousandunambiguouscontext-freegrammars. The Earleyparser[10]isanothergeneral-purposedynamicprogrammingalgorithmforparsingcontext- free grammars that executes in cubic time (O(n3)) in the general case, quadratic time (O(n2)) for unambiguous grammars,and linear time (O(n)) for almost all LR(k) grammars. Free from the requirement to develop efficient linear-time parsing algorithms, researchers have developed many powerful nondeterministic parsing strategies following both the top-down approach (LL parsers) and the bottom-up approach (LR parsers). Followingthetop-downapproach,Packratparsers[12]andtheirassociatedParsingExpression Grammars (PEGs) [13] preclude only the use of left-recursive grammar rules. Even though they usebacktracking,packratparsersarelinearratherthanexponentialbecausetheymemoizepartial results,they attempt the alternativeproductions inthe specifiedorder,andthey acceptonly the firstonethatmatchesaninputposition. Infact,LL(*)isanoptimizationofpackratparsing[35]. Followingthe bottom-upapproach,GeneralizedLR(GLR)is anextensionofLRparsersthat handles nondeterministic and ambiguous grammars. GLR forks new subparsers to pursue all possible actions emanating from nondeterministic LR states, terminating any subparsers that lead to invalid parses. The result is, again, a parse forest with all possible interpretations of the input. GLR parsers perform in linear to cubic time, depending on how closely the grammar conforms to the underlying LR strategy. The time required to run the algorithm is proportional to the degree of nondeterminism in the grammar. Bernard Lang is typically credited with the 4 original GLR idea [24]. Later, Tomita used the algorithm for natural language processing [47]. Tomita’s Universal parser [48], however,failed for grammars with epsilon rules (i.e. productions withanemptyright-handside). Severalextensionshavebeenproposedthatsupportepsilonrules [33, 44, 17, 30]. 2.4. Lexer and Parser Generators Lexerandparsergeneratorsaretools thattakea languagespecificationas inputandproduce a lexical analyzer or parser as output. They can be characterized by their input syntax, their ability to specify semantic actions, and the parsing algorithms the resulting parsers implement. Lex [25] and yacc [19] are commonly used in conjunction [26]. They are the default lexical analyzer generator and parser generator, respectively, in many Unix environments and stan- dard compiler textbooks often use them as examples, e.g. [2]. Lex is the prototypical regular- expression-based lexical analyzer generator, while yacc and its many derivatives generate LALR parsers. JavaCC [28] is a parser generator that creates LL(k) parsers, albeit it has been superseded by ANTLR [36]. ANTLR is a parser generator that creates LL(*) parsers. ANTLR-generated parsersare linear in practice andgreatly reduce speculation, reducing the memoizationoverhead of pure packrat parsers. The Rats! [16] packrat parser generator is a PEG-based tool that also optimizes memoiza- tion to improve its speed and reduce its memory footprint. Like ANTLR, it does not accept left-recursive grammars. Unlike ANTLR, programmers do not have to deal with conflict mes- sages, since PEGs have no concept of a grammar conflict: they always choose the first possible interpretation, which can lead to unexpected behavior. NLyacc [17] and Elkhound [30] are examples of GLR parser generators. Elkhound achieves yacc-like parsing speeds when grammars are LALR(1). Like PEG parsers, GLR parsers silently accept ambiguous grammars and programmers have to detect ambiguities dynamically [35]. YAJco [37] is aninteresting tool thataccepts, as input, a setof Javaclasseswith annotations that specify the prefixes, suffixes, operators,tokens, parentheses,and optionalelements common intypicalprogramminglanguages. Asoutput,YAJcogeneratesaBNF-likegrammarspecification for JavaCC [28]. Since YAJco is built on top of a parser generator, the language designer has to be carefulwhenannotatinghisclasses,asthe implicitgrammarheisdefininghastocomplywith the constraints imposed by the underlying LL(k) parser generator. 2.5. Model-Based Language Specification Initsmostgeneralsense,amodelisanythingusedinanywaytorepresentsomethingelse. In suchsense,agrammarisamodelofthelanguageitdefines. InSoftwareEngineering,datamodels arealsocommon. Datamodelsexplicitlydeterminethestructureofdata. Roughlyspeaking,they describe the elements they represent and the relationships existing among them. From a formal pointofview,itshouldbenotedthatdatamodelsandgrammar-basedlanguagespecificationsare notequivalent,eventhoughbothofthemcanbeusedtorepresentdatastructures. Adatamodel can express relationships a grammar-based language specification cannot. A data model does not need to comply with the constraints a grammar-based language specification has to comply with. Typically, describing a data model is generally easier than describing the corresponding grammar-basedlanguage specification. 5 In practice, when we want to build a complex data structure from the contents of a file, the implementation of the language processor needed to parse the file requires the software engineer tobuildagrammar-basedlanguagespecificationforthedataasrepresentedinthefileandalsoto implementtheconversionfromtheparsetreereturnedbytheparsertothedesireddatastructure, which is an instance of the data model that describes the data in the file. Wheneverthelanguagespecificationhastobemodified,thelanguagedesignerhastomanually propagate changes throughout the entire language processortool chain, from the specification of the grammar defining the formal language (and its adaptation to specific parsing tools) to the corresponding data model. These updates are time-consuming, tedious, and error-prone. By making such changes labor-intensive, the traditional language processing approach hampers the maintainability and evolution of the language used to represent the data [21]. Moreover,it is not uncommon for different applications to use the same language. For exam- ple, the compiler, different code generators, and other tools within an IDE, such as the editor or the debugger, typically need to grapple with the full syntax of a programming language. Unfortunately, their maintenance typically requires keeping several copies of the same language specification synchronized. The idea behind model-based language specification is that, starting from a single abstract syntax model (ASM) that representsthe core concepts in a language,languagedesigners cande- velop one or several concrete syntax models (CSMs). These CSMs can suit the specific needs of the desired textual or graphicalrepresentationfor the language sentences. The ASM-CSM map- pingcanbeperformed,forinstance,byannotatingtheabstractsyntaxmodelwiththeconstraints needed to transform the elements in the abstract syntax into their concrete representation. This way, the ASM representing the language can be modified as needed without having to worry about the language processor and the peculiarities of the chosen parsing technique, since the corresponding language processor will be automatically updated. Finally, as the ASM is not bound to a particular parsing technique, evaluating alternative and/or complementary parsing techniques is possible without having to propagate their con- straints into the language model. Therefore, by using an annotated ASM, model-based language specification completely decouples language specification from language processing, which can be performed using whichever parsing techniques are suitable for the formal language implicitly defined by the abstract model and its concrete mapping. AdiagramsummarizingthetraditionallanguagedesignprocessisshowninFigure1,whereas thecorrespondingdiagramforthemodel-basedapproachisshowninFigure2. Itshouldbenoted thatASMs representnon-treestructureswheneverlanguageelementscanreferto otherlanguage elements, hence the use of the ‘abstract syntax graph’ term. The ASM is built on top of basic language elements, which can be viewed as the tokens in the model-driven specification of a language. Model-driven language processing tools such as ModelCC provide the necessary mechanisms to combine those basic elements into more complex language constructs, which correspond to the use of concatenation, selection, and repetition in the syntax-driven specification of languages. When the ASM represents a tree-like structure, a model-based parser generator is equivalent to a traditional grammar-based parser generator in terms of expression power. When the ASM represents non-tree structures, reference resolution techniques can be employed to make model- based parser generators more powerful than grammar-basedones [38], as we will see in the next 6 Context-Free Attribute Conceptual Grammar Grammar Model e.g. BNF instance instance of of Textual input output Abstract Parser Syntax Representation Tree Concrete Syntax Model Abstract Syntax Model Figure1: Traditionallanguageprocessing. Context-Free Conceptual Grammar Model e.g. BNF instance instance of of Textual input output Abstract Parser Syntax Representation Graph Concrete Syntax Model Abstract Syntax Model Figure2: Model-basedlanguageprocessing. section. For instance, in ModelCC, the constraints imposed over ASMs to define a particular ASM- CSMmappingcanbedeclaredasmetadataannotationsonthemodelitself. Nowsupportedbyall themajorprogrammingplatforms,metadataannotationsareoftenusedinreflectiveprogramming and code generation [14]. Table 1 summarizes the set of constraints supported by ModelCC for establishing ASM-CSM mappings between ASMs and their concrete representation in textual CSMs. It should be noted that model-based language specification techniques allow lexical and syn- tactic ambiguities: each language element is defined as a separate and independent entity, even when their patternspecificationorsyntactic specificationare inconflict. Therefore,model-based languagespecificationtechniquesrequirealexicalanalysisalgorithmwithambiguitysupportand a parsing algorithm with lexical and syntactic ambiguity support. When a language element in a model is composed of only optional members, epsilon produc- tions (such as E := ǫ) arise in the grammar. Furthermore, the combination of selection and concatenation may produce grammar cycles (such as A:= c, A := B, and B := A). The formal grammars of languages specified using model-based techniques may also contain constraints on associativity, composition, and precedence, and custom constraints. Therefore, a scanner and a parser that supports such requirements are needed. 7 Constraints on... Annotation Function @Pattern Pattern matching definition of basic language elements. ...patterns @Value Field where the recognized input element will be stored. @Prefix Element prefix(es). ...delimiters @Suffix Element suffix(es). @Separator Element separator(s) in lists of elements. @Optional Optional elements. ...cardinality @Minimum Minimum element multiplicity. @Maximum Maximum element multiplicity. @Associativity Element associativity (e.g. left-to-right). ...evaluation @Composition Eager or lazy composition for nested composites. order @Priority Element precedence level/relationships. ...composition @Float When element member position may vary. order @FreeOrder When all the element members positions may vary. @ID Identifier of a language element. ...references @Reference Reference to a language element. Custom @Constraint Custom user-defined constraint. constraints Table1: Themetadata annotations supportedbytheModelCCmodel-basedparsergenerator. (-|\+)?[0-9]+ Integer (-|\+)?[0-9]+\.[0-9]+ Decimal \. Point \# Hash \$ Dollar Figure3: Regularexpressionsandtokennamesinalexically-ambiguoustokenspecification. 3. The Lamb scanning algorithm Lamb[39]isascanningalgorithmwithambiguitysupport. Lambalsosupportstokenprecedence constraints and the hard-coded specification of custom pattern matchers and lexical or semantic constraints. The power of the Lamb scanning algorithm resides in the usage of lexical analysis graphs to store and output the scanning results. In these graphs, each token is linked to its preceding and following tokens and there may also be several starting tokens. Each path in a lexical analysis graphs represents a different sequence of tokens that can be found within the input string. For example, the token specification listed in Figure 3 is lexically-ambiguous, since any se- quenceofdigitsseparatedwithpointscouldbeconsideredeitherDecimal tokensorInteger Point Integer token sequences. Let us consider, for example, the “5.2 $ 8.4” input string. When using a traditional scanning algorithm, the developer can either assign the Integer token a greater priority than the Decimal 8 Figure4: Lexicalanalysis,asproducedbyatraditionalscanningalgorithm,whentheInteger tokenhasagreater prioritythantheDecimal token. Figure5: Lexicalanalysis,asproducedbyatraditionalscanningalgorithm,whentheDecimal tokenhasagreater prioritythantheInteger token. Figure6: Lexicalanalysis,asproducedbyLamb,assumingthatDecimal andInteger tokensdonothavedifferent priorities. token or vice versa. The respective interpretations of the “5.2 $ 8.4” string are shown in Figures 4 and 5. Unless specified by the language designer, Lamb does not impose token precedences and it is able to capture all the four possible token sequences in the form of a lexical analysis graph, as shown in Figure 6. Lamb is able to recognize ambiguities that involve tokens of different types that overlap, in contrast to traditional approaches such as the Schr¨odinger’s token [4], which cannot be applied to overlappingtokens as itonly allowsfor stringsto havea superpositionoftokentypes. Indeed, in certain applications, even a string such as “52” could be interpreted as ambiguous: It could correspondeither anInteger ora sequence of twoInteger tokens. Lamballows choosingbetween a greedy pattern matching policy, in which given several tokens of the same type that start in the same position index, only the longest match will be considered; and an exploratory pattern matching policy, in which given several tokens of the same type that start in the same position index, all of them are considered. In Section 4, we will illustrate the result of parsing this lexical analysis graph. TheLambscanningalgorithmconsistsoftwophases: thescanningphase,whichrecognizesall the possibletokensinthe inputstring(Subsection3.1); andthe lexicalanalysisgraphgeneration phase,whichcomputesthesetsofprecedingandfollowingtokensforeachtoken(Subsection3.2). 3.1. The Scanning Phase The Lambscanning phase matches a list ofpattern matcherswith the input string. It can be configured to follow one of these two matching policies, depending on the language features: • Greedy pattern matching policy. Given several tokens of the same type that start in the same position index, only the longest match will be considered. This policy avoids the generation of huge lexical analysis graphs, and can only be used when no tokens in 9 the language can be broken up solely into two or more tokens of its same type with no additional delimitation. If a token could be broken up into two or more tokens of its same type, the greedy policy wouldskip the subtokens. For example, scanning the string “4912” for Integer tokensby followingthe greedypattern matching policy wouldperforma greedy matching and would yield the token “4912”. As the only found token starts at the first position in the input string and ends at the last position in the string, it is the only entity that could be delimiting any other tokens. As there is nothing before the first position in the input stringorafter the lastpositioninthe input string,there arenotany moretokens in it. • Exploratory pattern matching policy. Givenseveraltokensofthesametypethatstart in the same position index, all of them are considered. While this policy cannot render a lexical analysis incorrect, it allows the generation of a exponentially huge lexical analysis graphs,andisrequiredwhenanytokensinthelanguagecanbe brokenupintotwoormore tokens of its same type with no additional delimitation. For example, scanning the string “4912”forInteger tokensby followingthe exploratorypatternmatchingpolicy wouldyield all the tokens “4”, “9”, “49”, “1”, “91”, “491”,“2”, “12”,“912”, and “4912”. Whenperformingthe lexicalanalysis,Lambkeepsaforbiddentokenlistandastate valuefor each position in the input string. The forbidden token list stores constraints on the generation of different token types. The state value determines whether a position index is a valid starting position for matchings (MATCH) or not (SKIP). In the latter case, it should be noted that the character stored in that position can take part in matchings that started some positions before in the input string. ThegreedypatternmatchinginitializesthestatetoMATCH forthefirstpositionoftheinput stringandtoSKIP forthe restofthepositionsoftheinputstring. Foreachpositionindexofthe inputstring,ifitsstateisMATCH,everypatternmatchercorrespondingtoatokenthatisnotin the forbidden token lists is applied in descending order of precedence. The pattern matchers try to greedily match the single longest matching possible that starts in that position. Whenever a matching is found, it adds the tokens it precedes to the forbidden token lists for all the positions of the matched text. The state of the position index that follows the last symbol of the token is set to MATCH, so that new tokens can start at that position. The exploratorypattern matching assumes the state is MATCH for all the input string posi- tions. Every pattern matcher is applied, in descending order of precedence, for each position in the input string. The pattern matchers try to match every possible matching that starts in that position. Whenever a matching is found, it adds the tokens it precedes to the forbidden token lists for all the positions of the matched text. Either if the pattern matching policy is greedy or exploratory, this phase has a theoretical O(ln2) order of efficiency, being n the input string length and l the number of matchers in the scanner, even when the string can be tokenized in up to ln ways. 3.2. The Lexical Analysis Graph Generation Phase The sets of preceding and following tokens of an x token are defined in Equation 1, being a,b,c tokens and xstart and xend the starting and ending positions of the x token in the input string. 10