Mark van den Brand
Department of Software Engineering, CWI
Kruislaan 413, 1098 SJ Amsterdam, The Netherlands
Alex Sellink![[*]](http://www.wins.uva.nl/pict/latex2html/foot_motif.gif)
, Chris Verhoef
University of Amsterdam,
Programming Research Group
Kruislaan 403, 1098 SJ Amsterdam, The Netherlands
markvdb@cwi.nl, alex@wins.uva.nl, x@wins.uva.nl
We evaluate the parsing technology used by people working in the reengineering industry. We discuss parser generators and complete systems like Yacc, TXL, TAMPR, REFINE, CobolTransformer, COSMOS, and ASF+SDF. We explain the merits and drawbacks of the various techniques. We conclude that current technology may cause problems for the reengineering industry and that modular and/or compositional parsing techniques are a possible solution.
Categories and Subject Description:
D.2.6 [Software Engineering]: Programming Environments--Interactive;
D.2.7 [Software Engineering]: Distribution and Maintenance--Restructuring;
D.3.4. [Processors]: Parsing.
Additional Key Words and Phrases: Reengineering, System renovation, Parsing, Generalized LR parsing, compositional grammars, modular grammars.
A hardly controversial statement in the reengineering community is that in order to reengineer software it is convenient to parse it. Maybe due to the overall agreement on this issue, the question which parsing technology is the most suitable for reengineering purposes is not addressed. Indeed, there are well-established techniques for generating parsers from a grammar. They were developed with a focus on the fact that the grammar was known in advance and not likely to change continuously. After all, once a language is defined and a parser is generated that is the end of the story. The condition that the grammar of the language is known in advance is not satisfied in the field of reengineering. Let us first explain that this is the case and then what the consequences are in the realm of proven parser technology.
It is not the case that when, say COBOL, needs to be reengineered that we can use an existing grammar and then parse this COBOL source. For, there is a myriad of COBOL dialects, some of them are even home-brewed. Furthermore, there are many extensions to COBOL, for instance, embedded CICS, SQL, and/or DB2. This implies that there is a good chance we have to write a parser before we can start a reengineering project. To phrase it informally, it seems that in reengineering the language is the variable and the problems are the constants: the Year 2000 problem or the Euro conversion problem occur in virtually every language. Since the language is not known in advance the original condition of well-established parser technology is not satisfied in the field of reengineering. To make the problems a bit more concrete we quote from the German home page of Micro Focus [7]:
german Beim Einsatz von Parsern stoßen Unternehmen in der BRD zumeist auf zwei Probleme: Zum einen sind Parser fast ausschließlich für Programmiersprachen wie COBOL, PL/1 und Assembler erhältlich. Eine Entwicklung von Parsern für ``Nischen''-Sprachen rechnet sich für die Tool-Hersteller in der Regel nicht. Zum anderen stammen fast alle gängigen Parsing-Tools aus den USA - sie kommen deshalb mit den Eigenheiten der Entwicklungsumgebungen in deutschen Rechenzentren nicht zurecht. Auf den ``Zoo'' von Entscheidungstabellen, Programmgeneratoren und Meta-COBOL-Sprachen, der in den vergangenen 20 Jahren hierzulande entstanden ist, sind sie nicht vorbereitet. Der von diesen Werkzeugen erzeugte ``Meta''-Code wird von den gängigen Parsern nicht verstanden. Eine Migration dieses Codes zu ``echtem'', lesbarem COBOL-85-Code wäre oft zu risikoreich: Zum einen würden irreguläre Sprachelemente implementiert, zum anderen verhalten sich die verfügbaren Konverter oft nicht stabil. Drittens kommt hinzu, daß eine Migration zu COBOL-85 das Jahrtausendproblem zunächst nur auf eine ``modernere'' Sprache verlagert - nicht aber löst.
In the footnote we give the translation in English. Obviously, there is a great need for state-of-the-art parser technology to solve the problems like the ones addressed by Micro Focus.
A well-established technology for the generation of parsers is called LR-parsing. The most well-known implementations of this technology are the parser generator Yacc [25] and its GNU variant Bison. All these implementations share the property that the grammar that is specified in the above formalisms should be free of conflicts. We recall that there are two categories of conflicts. There is a so-called shift/reduce conflict, which means that there are two options, namely, an extra token can be shifted on the stack or a reduction can be made by application of a production rule. And there are reduce/reduce conflicts, meaning that two distinct reductions are possible. When defining a grammar using Yacc or Bison, it is necessary to remove the above conflicts. This is not a disaster when the language is fixed: as soon as the conflicts are resolved we are done. The problems occur when the grammar is continuously changing. It is not an exception that 50 conflicts arise as a consequence of adding a single grammar rule to a COBOL grammar. Some of these problems can be resolved by performing a retokenization in the preprocessing phase. This does not change the underlying structure of the grammar, which is an advantage. However, it means that the source code has to be transformed. The remaining problems can only be solved by modifying some context-free grammar rules. The effect of this is that the underlying structure of the grammar becomes more and more artificial, which is undesirable.
Removing a grammar rule is also a problem: apart from removing production rules also the changes to resolve conflicts should be removed: grammar rules and/or preprocessor fixes. This is quite some work and demands sophisticated version management, for instance using CVS [14]. In practice, such things do not happen: the legacy of a retokenization or grammar modification often remains in the grammar specification. In this way a grammar specification easily becomes an unmaintainable business-critical application that needs to be reengineered. Therefore, we consider current parser technology harmful when applied to reengineering purposes.
If a grammar can be constructed in more than one file using an import mechanism we call this property modularity. This is also a useful property in reengineering. In this way, it is possible build a repository of grammar components. So we can reuse grammar definitions. For a reengineering company it is convenient to have grammar components in a repository so that a parser for a specific reengineering project can be constructed on the fly. If we wish to construct it simply by importing a COBOL module and a CICS module.
We stress that the combination of compositionality and modularity is a desirable combination for reengineering purposes: modularity enables reuse and compositionality guarantees that the combined modules give rise to correct parsers. So if we import COBOL and CICS modules to obtain a COBOL/CICS grammar and the grammars are compositional, we can effortlessly generate a parser for them.
The problem with current parsing technology is that it is not
compositional: most of the parser generators do not parse arbitrary
context-free grammars but certain subclasses that are not closed under
compositionality. They are mostly indicated with abbreviations like
LL, LL(1), LL(k), LR, LR(1), LR(k), LALR, LALR(1),
LALR(k), etc. We recall that the first L in LL or LR stands
for left-to-right scanning of input, and that the R in LR stands
for rightmost derivation in reverse, the second L in LL stands for
leftmost derivation, the k stands for the number of input symbols of
lookahead that are used. If there is no k we assume k=1. Finally,
the LA stands for lookahead and is synonym with the (k) postfix,
therefore it is sometimes omitted. For all these classes an efficient
parsing algorithm exists. Therefore, we speak of proven technology:
it is robust and efficient. The problem with those subclasses is that
they are not compositional. This means that, for instance, combining
two LR grammars does not imply that the resulting grammar is also
an LR grammar. So, if we use an LR
parser generator and combine two LR grammars, we can not successfully
use the generator again. First we have to resolve the conflicts
in the LR table. This is a fundamental problem of the process of
modifying grammars for reengineering purposes: the grammars are subject
to continuous change. Let us give a small example. Suppose we have
the grammar consisting of the rules E ::= a B C, B ::= b, C ::=
c and a grammar constisting of E ::= a B D, B ::= b, D ::= d.
Both grammars are LR. If we combine them, we obtain the grammar E
::= a B C, E ::= a B D, B ::= b, C ::= c, D ::= d, note that combining is
just simply the set-theoretic union. The resulting grammar is no longer
LR because we need a look ahead of more than 1 to decide which rule
matches a b c. For other combinations, similar examples exist.
For more details on these issues and well-established parsing technology
we refer to [2], [1], or [43].
Current parser technology is also not modular. This is not very surprising since the lack of compositionality disencourages modular specifications of grammars. However, with the aid of a preprocessor it is possible to obtain a form of noncompositional modularity. In the next section we will see an example where Siber Systems uses noncompositional modularity.
%define, %ifdef, %endif, %include).
BtYacc can be downloaded for free from the home page of Siber Systems.
BtYacc is not compositional.
:-}Öbviously, this parser is
both compositional and modular. At the time of writing this paper they
are working on the incremental part of the parser generator.
From the above observations we can draw the conclusion that it is more and more recognized that current parser technology gives many problems in the field of reengineering languages like COBOL. We expect that this is due to the fact that such languages come in many dialects, with many extensions, and with home brewed constructs. Another observation is that companies begin to solve their parse problems using compositional and/or modular techniques. We note that in [10] it has been argued that generic language technology like modular GLR parsing is necessary for reengineering purposes. In the next section we will elaborate on this technology.
Generalized LR parsing is sometimes called Tomita parsing. We prefer
to use generalized LR parsing since the result is due to Lang, at least
not to Tomita. As far as we know, Rekers [34] was the first who
implemented the GLR parsing algorithm as part of a system intended for
practical applications (the ASF+SDF Meta-Environment). Also Rekers extended the algorithm
to the full class of general context-free grammars. The algorithm that
Tomita presents loops on cyclic grammars, which was solved by Rekers.
Furthermore, in [30] a modification to the algorithm that
Tomita describes was made--a modification that is present in Rekers'
implementation. The GLR algorithm returns a forest of parse trees,
however, for reverse engineering purposes we are only interested in
one tree. Therefore, a number of syntactic disambiguation rules must
be applied to reduce the number of yielded trees. This can be done by,
e.g., using the associativity and priority rules for binary operators, for
more details see the SDF reference manual [20]. If eventually
more than one parse tree is left over, this is reported to the user and
she is obliged to make a selection. The grammar rules which cause this
ambiguity are reported as well, so in this way the ambiguities in the
grammar are located.
Thus far, we are not aware of other systems than the ASF+SDF Meta-Environment that have well-tested and heavily used implementation of a GLR parser generator as part of a system. We note that the latest version of the so-called Ibpag2 system (Icon-Based Parser Generation System 2) can handle GLR grammars for Icon. Icon is a high-level, general purpose programming language [17].
The GLR algorithm uses an ordinary LR parse table. This table may contain shift/reduce and/or reduce/reduce conflicts. The GLR algorithm operates in exactly the same way as the LR algorithm, until either a shift/reduce or reduce/reduce conflict in the parse table is encountered. The algorithm forks as many parses as there are possibilities to proceed. If a conflict was due to the need for lookahead, those forked parses will die. All these parses proceed in parallel but synchronize on the shift actions. This gives rise to the possibility of merging parses which are in the same LR state. We note that the above algorithm is a special case of work that has been presented by Lang [27].
Next we compare the performance of the GLR algorithm to Earley's algorithm [16]. Earley's algorithm can handle ambiguities as well. Below 107 ambiguities the GLR parsing algorithm wins from the Earley algorithm and above this number the Earley algorithm wins. See [34] for details.
From all these measurements, the conclusion can be drawn that when there is not a single conflict in a grammar the cheapest solution is to use an existing LALR parser generator like Yacc. When the number of ambiguities is extremely high, it is best to use Earley's algorithm--it misbehaves on conflict-free grammars. In most practical reengineering cases the number of ambiguities is far less than 107 but more than more than zero (viz. the 357 conflicts in the Pascal grammar). So in those cases it is a good idea to use GLR parsing technology, as we will see shortly in the next section.
In [13], we propose a methodology to obtain a COBOL grammar for reengineering purposes. As an example we implemented an OS/VS COBOL grammar using the ASF+SDF Meta-Environment that contains Rekers' [34] implementation of incremental Generalized LR parsing. The ASF+SDF Meta-Environment also contains incremental generation of lexical scanners [23]. Those features made this system for us a perfect candidate to prototype our ideas on parsing for reengineering. We think that successfully defining a COBOL grammar plus some dialects and extensions using GLR parsing technology gives clear evidence that this technology scales up to real-world applications. We have no no maintenance problems and we can easily extend or restrict grammar definitions.
We took care of handling dialects of COBOL in [11]. Due to the modularity and the compositionality we were able to simply modify the grammar defined in [13] to a grammar that parsed both dialects, which is convenient for dialect conversions. To give the reader an idea of the modularity we depicted the import-graph of the grammar in Figure 1. An arrow from module A to B means that all grammar rules of module A are imported in module B. The module PROGRAM, depicted at the right of Figure 1 is the top module of the definition. This module gathers all the grammar rules that are describing the syntax of the four divisions of COBOL. Similarly, the top modules IDENT-DIV, ENV-DIV, DATA-DIV, and PROC-DIV gather the grammar rules that are specific for the four divisions that are available in COBOL. In the modules IDENT-BASIS, ENV-BASIS, DATA-BASIS, and PROC-BASIS, the structure of those divisions is defined. In twelve modules ranging from INFO to RU-STAT we define the more local syntax, like MOVE statements, or IF statements. The four BASIS modules import the module PHRASES. This module gathers the grammar part that is not specific to a particular division. Natural numbers, decimals, strings, literals, identifiers, data-names, arithmetic and logical expressions (A-EXP, L-EXP), relation symbols, predicates, pseudo-text, copy statements, and on the lowest level comments. This module contains the grammar rules for layout and comment.
We also constructed a CICS grammar using the methodology reported on in [13]. It took two hours to construct the CICS grammar, to merge it with a COBOL grammar and to test it on a COBOL program that contained all the CICS code that was available in a 70 KLOC COBOL/CICS mortgage system. For another project we needed to extend a certain COBOL dialect with SQL. It took eight hours to construct a grammar for embedded SQL, to integrate it, and to test it on the system. We stress that--due to the GLR parser generator--not a single ambiguity had to be solved during the extension of CICS or SQL. Note that with this approach we are able to provide multilingual support for reengineering tools. For an example of tools for reengineering a COBOL/CICS system we refer to [11].
In Figure 2 we depict a hyper-graph of a typical project grammar. It is a hyper-graph since the nodes of this graph can represent themselves again a (hyper-)graph. For instance, the COBOL node in our hyper-graph represents the entire COBOL import-graph as depicted in Figure 1. The other nodes represent grammars for possible extensions to COBOL, like embedded SQL, embedded CICS, embedded DB2, a yet unknown extension, or some temporal nonstandard extension like the Ampersand module that we will discuss in Section 5. The switches in Figure 2 denote the possibility to add or remove extensions to COBOL. The implementation of this switchboard is just a simple module that contains the right imports for a particular project. The module PROJECT-GRAMMAR for the above situation consists of the following line:
imports COBOL DB2 Ampersand
Addition of CICS and removal of DB2 and Ampersand for another project is simply a matter of changing the import structure:
imports COBOL CICS
Intuitively, we see this file as a switchboard to combine COBOL with arbitrary extensions at wish.
We use this switchboard to reuse large parts of grammars to construct new ones. We believe that our approach gives some evidence that modular GLR parsing provides the necessary flexibility for reengineering purposes. At least, we are building a repository of grammar modules that can be effortlessly combined at wish to readily parse new projects.
Reusability of parsers is not easy. Apart from the lack of modularity, a reason for this is that the input and output formats of various parsers do not necessarily fit to the front-ends of reengineering tools. In [35] this problem is already mentioned: they propose that parsing should be a separate component for a reverse engineering tool in order to deal with dialects. They write that:
Expanding a tool's capabilities to include additional source languages and additional analyses, can often be quite difficult. The statement that ``all you have to do is add a new parser'' is deceptively appealing.
So not only parsing of obscure dialects is a problem, but also the connection of these parsers to existing tools.
Another problem is that most parsers have been used in order to be the front-end of a compiler so sometimes they are completely integrated within this implementation. If this is the case it is not possible to reuse the parser of that particular language for reengineering purposes.
The parser that we use for reengineering purposes has as input format SDF [20]. We recall that this stands for Syntax Definition Formalism. The output format is ATF, this stands for Annotated Term Format [9]. ATF is specifically designed for the data exchange between (possibly) heterogeneous or distributed components in a software system. It is a powerful format in which it is possible to represent, for instance, parse trees that can be annotated with all kinds of information like textual coordinates, access paths, or the results of data flow, control flow or other program analysis. It is not hard to transform a term in ATF to another output format. In this way our parser generator can, in principle, be used as a front-end for other tools. The ASF+SDF Meta-Environment is primarily an interactive system, but it can be run batch oriented using a small shell script. So in principle it can be used as a GLR parser generator. We use the batch oriented mode to automatically restructure complete systems. We are interested in the in- and output formats (if any) and the implementations that Reasoning and Semantic Designs are currently implementing; so we can compare them to the implementation in the ASF+SDF Meta-Environment.
[42] discusses scannerless GLR parsing. The idea of scannerless parsing is due to Salomon [36,37]. Scanning and parsing are separate processes. The parser asks the scanner to give the next lexical token. However, at the lexical level there can be ambiguities as well (for instance the longest-match ambiguity [36]). The scanner has to make a decision that can be in conflict with what the parser expects. This can lead to syntax errors in correct programs. This problem is solved by using scannerless parsing because the parser takes over the scanning and makes the disambiguation decisions. The basic idea is to transform the lexical syntax (defined by regular expressions) into context-free grammar rules. So scannerless GLR parsing is even more desirable for reengineering. This is not implemented in the ASF+SDF Meta-Environment. It is the intention that a scannerless GLR parser generator will become a component in the new version of the ASF+SDF Meta-Environment. A prototype is both algebraically specified in ASF+SDF and implemented in C [42]. It works on small examples but some problems need to be solved.
According to [37], scannerless parsing is efficient since it can be implemented using a simple two-stack push-down automaton. Indeed this is efficient: push and pop operations on a stack are inexpensive.
imports Program
exports
sorts Id-ampersand
lexical syntax
Left* [&]+ Right* -> Id-ampersand
context-free syntax
Id-ampersand -> Id
Before we continue, let us explain this module. We import the entire COBOL grammar by importing the top module in COBOL called Program. We export the new sort Id-ampersand so that tools like a parser can use it. The sorts Left and Right are defined in the low-level module ID that defines identifiers for COBOL. They are known to the ampersand module due to the import structure of the COBOL grammar, see Figure 1. They represent that an identifier in COBOL may not start with a minus sign and may not end with a minus sign. The same holds for the identifiers containing the ampersands. In the context-free syntax definition we then lift this special sort to the known sort Id, so that not only normal identifiers are recognized but also if they contain an ampersand. Using this additional module we can recognize identifiers like ABC-&&&&&&&-DEF.
The merit of this modular approach is that for this particular project we added it to the switchboard. The core grammar is not polluted with this idiosyncratic syntax. In fact, the switchboard approach enables us to easily undo a change to the grammar. Without modularity it would have been necessary to modify the identifiers inside the COBOL definition, which is dangerous: after quickly modifying the grammar and resolving the conflicts, the resulting grammar is often not changed back to its original form due to timing constraints. Tomorrow someone else uses an ampersand-sign for another purpose and then it becomes more and more difficult to maintain such a grammar. A number of such changes leads to a grammar with a maintenance problem: it will become harder and harder to resolve conflicts. We expect that in the near future serious reengineering companies will face the fact that their own business-critical applications need to be reengineered. Hence, the title of this paper: we believe that mainstream technology indeed can be harmful for reengineering companies. To phrase it informally: if such grammars exist, we believe them to have a year 1999 problem: before that year they need to be reengineered so that they can parse and analyze the programs with a possible year 2000 problem. Therefore, we do not believe it to be a coincidence that, for instance, Reasoning or Semantic Designs are implementing GLR parsing technology.
parser generator.
