Software analysis often relies on pattern matching in terms of Abstract Syntax Trees (ASTs), but AST patterns are known to be tedious to specify. Concrete syntax patterns with placeholders have been proposed as a user-friendly alternative. Several designs for this proposal have been implemented, but these typically focus on specific parsing technologies. In this paper we explore the overarching challenges of specifying AST patterns using concrete syntax with placeholders. Using our experience with industrial applications, we take the perspective of an analyst who creates concrete syntax patterns to find matches in a code base. We identify two specification challenges: (1) understanding the underlying AST structure, and (2) ambiguities caused by placeholders. For designs based on black-box parsers we also inventorize the challenge of (3) encoding and recognizing the placeholders in concrete syntax patterns. We illustrate these challenges with examples in the Ada and C/C++ programming languages. Our results can serve as warnings to users of concrete syntax patterns, as additional requirements for parser front-ends, as attention points for language specifications, and as starting points for further research on pattern matching.
Pattern matching on Abstract Syntax Trees (ASTs) is used widely for analyzing software [
As explained in [
The idea of “native patterns” [
We study AST matching based on concrete syntax patterns. The ASTs are matched structurally, but
the AST patterns are described using concrete syntax. Some pattern fragments, each corresponding to
adjacent AST nodes/attributes, can be replaced by meta-language placeholders. As a convention, similar
to [
if ∼ c then ∼ *stats; else ∼ *stats; end if;
Concrete syntax patterns have been implemented in, e.g., Stratego, TXL, and Rascal. Their designs
for using concrete syntax are described in, e.g., [
Regarding the first approach, [
In this paper we discuss our experience with concrete syntax for AST patterns from industrial
reengineering projects. [
In this paper we focus on specifying placeholders inside a single concrete syntax pattern, and ignore aspects like: • Dealing with macros and pre-processors, • Meta-language fragments beyond only placeholders (e.g., more complex expressions), • Linked find/replace patterns for code transformations.
Although the goal of “pattern matching with concrete syntax is WYSIWYG” (what you see is what you
get) [
These are overarching challenges for AST matching based on concrete syntax patterns. We link these challenges to specific designs in Section 5. Conclusions and future work can be found in Section 6.
Concrete syntax patterns provide a convenient alternative for writing AST patterns. In this section, we illustrate that users of concrete syntax patterns are still, sooner or later, confronted with the formal language structure and/or AST, which may be unfamiliar to them. This can happen in two phases: • Specification of the concrete syntax patterns; • Post-processing of AST matches from the code base.
As far as we know, this challenge does not get attention in the literature on implementing concrete syntax patterns. In the subsections, we identify groups of related issues. We frequently discuss diferences between parsers, even though our goal is not to use the same pattern with diferent parsers. Our goal is to indicate dependencies on implementation decisions from specific parsers, which get exposed to users of concrete syntax patterns.
Even experienced language users may be surprised by the AST structures of familiar languages. For example, look at the C++ declaration pattern
∼ t x which consists of a specifier ∼ t and a declarator x. Suppose we try to match this pattern with the following C++ code fragments: • int x is a match; • const int x and static int x are also matches, as type qualifiers like const and storage classes like static are part of the specifier; • int* x and int& x are no matches, as pointer operators like * and & are part of the declarator. The last two categories may surprise many C++ developers that did not study the formal language specification of C++.
Sometimes there are diferences between related constructs in diferent languages. For example, AST nodes for if-statements in C++ just contain a condition, then-clause and (optional) else-clause. However, in Ada there is an additional (possibly-empty) list of elsif-clauses, each with a condition and statement, which semantically correspond to else-clauses with nested if-statements. This has an impact on concrete syntax patterns for Ada as the elif-clauses explicitly need to be considered.
Similarly, the AST of a case-statement in Ada consists of a condition and a list of when-clauses (containing statements), whereas the AST of the related switch-statement in C++ consists of a condition and a list of statements (including possibly-nested case- and break-statements, but not grouped by case-statement). This has an impact on the post-processing of AST matches, even though C++ code often does not use the full flexibility of the language.
There are also diferences in multi-variable declarations. A multi-variable declaration in Ada, such as int x, y := 42; consists of a list of identifiers and a single optional expression as initial value for all variables. A multi-variable declaration in C++, such as consists of a list of declarators, each consisting of an identifier and an optional expression as initial value. Hence a pattern such as int ∼ *xs := 3; int ∼ *xs = 3; looks useful in Ada as placeholder ∼ *xs can be matched with multiple AST nodes in Ada. However, the similar pattern is suspicious in C++, as placeholder ∼ *xs can only be matched with a single AST node in C++.
The challenge discussed in this subsection is caused by matching using the programming languge’s
AST. This challenge may (to some extent) be solvable using diferent matching algorithms like [
The representation of the AST by a specific parser also has an impact. For example, in CDT the AST node type for unary operators is also used to represent prefix operators, postfix operators, parentheses and special operators like noexcept(. . .), thus abstracting from their diferent concrete syntax. This may give unexpected matching results, as C++ expression pattern ∼ op x matches ++x, x++, (x) and noexcept(x). Moreover C++ function call expression pattern ∼ func(∼ expr) does not match noexcept(x).
Another example is the representation of if-then and if-then-else statements. We could imagine the use of diferent AST node types for these statements, but have only seen a single node type for both statements in the studied parsers. However, in CDT the else-clause is represented as a single statement node, which is null if there is no else-clause. In Libadalang the else-clause is represented by a list of statement nodes, which is empty if there is no else-clause. So in Ada, the pattern
if ∼ c then ∼ *ts; else ∼ *es; end if; indicates an optional else-clause, as ∼ *es denotes any number of AST nodes, which may be counterintuitive from the concrete syntax. This could be solved by introducing a notation like ∼ +es to denote a placeholder for a non-empty list (1..* ) of AST nodes/attributes.
Similarly, a qualified name a.b.c.d could be represented as a list [a, b, c, d] or as a tree ((a, b), c), d). This impacts the behavior of placeholders for lists of nodes, e.g., a.∼ *ps.d. Only in case of a list representation, ∼ *ps can consist of list of nodes.
Finally, C++ type qualifiers, like const and volatile, are semantically order-independent. CDT stores them not as a list, but as a boolean attribute per possible qualifier. Hence const volatile int x and volatile const int x have identical ASTs, and hence match with each other, which may look counter-intuitive from the concrete syntax. Also the concrete syntax pattern ∼ *qs int x cannot be used to specify a declaration with any combination of type qualifiers, as ∼ *qs expects an (order-dependent) list. Side note: it may also be problematic because all qualifiers are reserved words, but that is a separate issue that we will address in Section 4.1.
The challenge discussed in this subsection is caused by design decisions from specific languages and
parsers. This challenge may (to some extent) be solvable by taking AST matching into account during
language and parser design; see also the suggestion from [
In Ada, function calls without arguments must omit the bracket pair () in the concrete syntax. In the
AST from Libadalang, this does not lead to a FunctionCall node, but to an Identifier node similar to a
variable reference. According to [
In addition, decimal literals in Ada can contain optional underscores, like 1_000, to increase readability, but these underscores are just syntactic sugar. The AST from Libadalang contains the concrete syntax of the decimal literal, so including any underscores, and hence the ASTs for 1000 and 1_000 difer. Also, the AST from CDT often stores the concrete syntax, causing that for example the long value 2147483648 is diferent from 2147483648L and that none of the following representations of the same integer value are identical: 0x10, 0X10, 16, 020, 0b10000, and 0B10000. Yet, the ASTs from CDT for the strings "con""cat" and "concat" are identical, despite their diferent concrete syntax.
Furthermore, explicit specifications often do not match their implicit, equivalent specification. In CDT, the type signed int does not match int and the function declaration with explicitly no parameters, i.e., void f(void);, does not match the implicit one, i.e., void f();.
Finally, you may not expect to find parenthesis nodes in an AST, but they are present in Libadalang and CDT. They are represented in diferent ways: Libadalang represents them using a dedicated ParenExpr node type, whereas CDT represents them as a unary operator. Thus parenthesis become relevant during pattern matching, as (x) and x are diferent.
The challenge discussed in this subsection is caused by design decisions from specific languages
and parsers. This challenge may (to some extent) be solvable by taking AST matching into account
during language parser design; see also the suggestion from [
Specifying AST patterns using concrete syntax with placeholders is less direct than using abstract
syntax, especially when aiming for compactness. In this section, we illustrate that this can easily lead to
ambiguities. In each subsection we identify a source of ambiguity. Additional types of C++ ambiguities
are documented in [
Some authors argue for “as few squiggles as possible” [
In general, users of concrete syntax patterns may not realise that they are writing a combination of two languages: the object and meta language. Our own practical experience is that it is useful to have clearly recognizable placeholder identifiers that are easily distinguishable from variable names.
The challenge discussed in this subsection is caused by trying to be too compact. This challenge can be solved by explicitly distinguishing these two types of identifiers.
In some approaches it is possible, or even required, to specify the AST node type of placeholders, either
explicitly or by convention on the placeholder name [
Consider the C++ pattern
∼ x; for a single statement. Would the type of the placeholder be (any) Statement; an ExpressionStatement; (any) Expression, nested inside an ExpressionStatement; an IdExpression; or a Name, nested inside an IdExpression?
Also consider the C++ enum-declaration pattern
enum { ∼ member } where placeholder ∼ member can have two possible AST node types, viz., Enumerator or Name: • enum { name } is a match for both AST node types.
• enum { name = 0 } is only a match for AST node type Enumerator.
• The more shallow AST node types, e.g., Enumerator, enable the matching of placeholders with composite AST nodes. Shallow refers to the distance to the root node of the AST, so not to the node type hierarchy, if any. • A single AST node type for each placeholder in a concrete syntax pattern avoids case analysis in the post-processing, e.g., to get the name in all possible matches.
The combination of these observations suggests to use for each placeholder the most shallow AST node type within the concrete syntax pattern, which is indeed useful in our experience. This means that for specifying an enum-member without a default value, either we would need placeholders with cardinality zero (0..0) in the meta language, or we need to filter out the unwanted matches as post-processing. The latter option keeps the meta language simpler, yet distributes knowledge over the pattern and the filter.
A similar situation occurs with the C++ function declaration pattern
void ∼ func(∼ x) { ∼ *body; } where placeholder ∼ x can have three possible AST types, viz., ParameterDeclaration, NamedTypeSpecifier, or Name: • void f(int) { } is a match for all three placeholder AST types.
• void f(int i) { } is only a match for a placeholder of type ParameterDeclaration. Again, the most shallow node type, so ParameterDeclaration, seems to be appropriate. To specify a parameter declaration without a name, we would again need placeholders with cardinality zero.
But what about the type of placeholder identifiers that occur more than once? Imagine the C++ pattern for swapping,
int ∼ t = ∼ x; ∼ x = ∼ y; ∼ y = ∼ t; in which each placeholder occurs twice. Recall that the pattern matching is applied on the AST, so the binding of names is not considered. The first occurrence of ∼ t has to be a Name, whereas all other occurrences of placeholders can be IdExpression and Name. Again, for each placeholder, the most shallow node type within the full scope of the pattern (so considering all occurrences of the placeholder) seems to be appropriate, so Name for ∼ t and IdExpression for ∼ x and ∼ y.
The examples so far can be addressed using the unique most shallow node type, but this is not always possible. Ada’s SubtypeIndication node type contains an optional constraint of a node type for which there are 5 possible subtypes. The 2 so-called composite subtypes, Index and Discriminant, just consist of a non-empty list, but with unrelated node types, DiscreteRange and DiscriminantAssociation, that can contain just a Name. So there is no unique most shallow node type of placeholder ∼ *xs in pattern subtype S is T(∼ *xs);.
The challenge discussed in this subsection is caused by trying to be too compact. This challenge could be solved by being explicit about the AST node types, but then we would loose some of the benefits of concrete syntax patterns. An alternative direction would be the use of generalized parsers that produce all possible ASTs; see also Section 5.1.
The parsing of languages like C++ requires name and type resolution to resolve ambiguities. For example, without context about symbols g and ∼ x, statement pattern is ambiguous in C++. It can be parsed both as a DeclarationStatement that declares a variable ∼ x of type g, and as an ExpressionStatement that invokes a method g with argument ∼ x. In both cases Name is a valid AST node type for placeholder ∼ x.
More C++ examples like this are known [
g(∼ x); ∼ x * ∼ y; that can be parsed as a DeclarationStatement, declaring a variable ∼ y of type ∼ x *, and as an ExpressionStatement, applying binary operator * to variables ∼ x and ∼ y. In these cases, we noticed that CDT prefers the parsing as DeclarationStatement, unless we provide a context in which ∼ x and/or ∼ y are declared as variables.
Such ambiguity aspects have an impact on the specification of concrete syntax patterns in languages like C++. If we want to disambiguate these patterns, there are two obvious candidates: 1. Solve the ambiguity by annotating some concrete syntax fragments, which are not necessarily placeholders and which possibly occur within a larger pattern, with the intended AST node type; 2. Solve the ambiguity using a parsing context with declarations of variables, functions, and types. Note that only the latter candidate requires no additional AST awareness from the user, apart from knowing when a parsing context needs to be specified. An alternative direction would be the use of generalized parsers that produce all possible ASTs; see also Section 5.1.
In Section 1 we have described two ways to obtain the ASTs for the patterns. In this section, we focus on approaches that use a black-box parser for the object language. Such approaches typically consist of three conceptual steps for handling concrete syntax patterns with placeholders:
2. Parse the concrete syntax into abstract syntax; 3. Recognize the placeholders within the abstract syntax.
• The user directly encodes the placeholders; • Specifications by users are translated into an encoding.
In this section, we identify challenges for directly encoding the placeholders; note that this is also relevant when designing a translation to an encoding. In each subsection we identify an aspect of such a placeholder encoding.
The notation ∼ p for placeholders in the previous sections suggests an encoding using an identifier in the object language, possibly with certain naming conventions. However, usually not all code fragments, that fully represent one AST node or a list of multiple AST nodes, in the object language can be replaced by a single identifier. In what follows we discuss two possibilities, which may also be combined, to address this issue: • Encode the placeholders using larger language fragments; • Parse the object language with suficient error recovery.
As a simple example of an encoding using larger language fragments, consider the pattern for any statement in C++. The pattern ∼ x is not a valid statement. Appending a semi-colon to the pattern, i.e., ∼ x;, results in a larger, yet valid statement pattern. This approach is taken by many designs based on black-box parsers.
A more complex example is the parameter declaration for functions in Ada. The Ada language does not support a single name to be used at the place of a parameter declaration, as in function fun(∼ *xs). Instead, a larger pattern like
function fun(∼ *xs : ∼ Dummy)
could be used, where the special identifier ∼ Dummy would indicate that we do not intend to match
a list of names with this specific type, but a list of (parameter) declarations. In the context of JSON,
the concrete holes in figure 2 from [
As an example of parsing with suficient error recovery, consider the C++ declaration pattern
class X { ∼ *f; };
which seems to be a natural way to specify a class with any number of declarations. Even with the extra
semi-colon at the end, this is strictly speaking not valid C++ code, but CDT’s error recovery [
Typical examples of concrete syntax fragments that often cannot be resolved in these ways are reserved words in the object language, as identifiers and reserved words are usually disjoint. Reserved words could be useful for matching C++ type classifiers such as const and volatile. However, recall that C++ type classifiers also give another problem in CDT as discussed in Section 2.2.
It is convenient if placeholder names can be used in the concrete syntax pattern without explicit declaration. Although in general the parsing may use declarations to resolve ambiguities, see also Section 3.3, in our experience the declarations of placeholder names can usually be omitted without causing problems. The capabilities of the used parsers to deal with incomplete input are key in this respect.
• Identifier: name to refer to the specific placeholder; • Cardinality: how many AST nodes to match, e.g., exactly one node, or any number of nodes; • AST node types (optional): type of the AST node(s).
The placeholders must be encoded in the concrete syntax, and afterwards be recognized in the
abstract syntax. As noted by [
The first approach might be preferable since each identifier from the language can be used for a variable and for a placeholder, only not both in the same pattern. However, object and meta-language identifiers are indistinguishable within a pattern (without considering the list of placeholder identifiers), a drawback already mentioned in Section 3.1, and a change might afect both the pattern and the list of placeholder identifiers.
For brevity reasons, the second approach may be preferable for manually-specified placeholder encodings. A drawback is that matching actual code is impossible when that code uses variable names that are in the predefined class of placeholder identifiers. In some cases you can use identifiers that are illegal according to the object language, but that are supported by the parser. In the Ada language, for example, identifiers cannot start with a dollar-sign, but Libadalang supports parsing of such identifiers. In these cases, the drawback is absent and the object and meta-language identifiers can be easily distinguished.
In this section, we discuss various approaches for concrete syntax patterns from the literature, and relate them to the specification challenges that we have presented. The subsections correspond to the two ways to obtain the ASTs for the patterns, as described in Section 1.
• Deterministic, like LR (Left-to-right Rightmost derivation) and LL (Left-to-right Leftmost derivation): produces one single AST; • Generalized, like GLR (generalized LR) and GLL (generalized LL): produces all possible ASTs. With respect to the ambiguities from Section 3, generalized parsers can be used to detect ambiguities in concrete syntax patterns, and to produce all possible interpretations. However, they may complicate the further processing of matching code fragments, by requiring filtering of duplicate matches, and case distinctions on specific AST node types.
“Most modern source transformations tools, such as ASF+SDF, Stratego, and DMS, use generalized LR
(GLR) parsers” [
Stratego in Spoofax uses an approach [
DMS ([
The approach from [
Coccinelle [
ClaiR (C Language Analysis in Rascal) [
Mooij et al. [
_p $p $S_p
__p $$p $M_p This table illustrates the intricacies of the placeholder naming scheme for diferent languages. The diferences originate from the identifier syntax that is supported by the parsers. The AST pattern matcher identifies and interprets the placeholders on-the-fly based on this naming convention. The following diagnosis information is available in case of failing matches: • formatted stack-trace with the related pattern and instance nodes, represented both in concrete and abstract syntax; • collected placeholders with their values.
We have identified two challenges for specifying concrete syntax patterns for AST matching: (1) understanding the underlying AST structure, and (2) ambiguities caused by placeholders. For designs based on black-box parsers we have also inventorized the challenge of (3) encoding and recognizing the placeholders. Our results can serve • as warnings to users of concrete syntax patterns, • as additional requirements for parser front-ends, • as attention points for language specifications, and • as starting points for further research on pattern matching.
Note that the third point relates to a research area that was already suggested by [
Future work could explore the debugging functionality in case of unexpectedly failing (or successful) pattern matches, and the detection of suspicious patterns as discussed in Section 2.1. Other directions could include ways to specify linked find/replace patterns for code transformations, and other matching algorithms for concrete syntax patterns.
Acknowledgments The authors thank Jeroen Ketema and Rosilde Corvino for sharing their
experience with the approach from [
Part of the research is carried out as part of the HybridAnalysis program under the responsibility of TNO-ESI in cooperation with Philips Image Guide Therapy Systems. The research activities are co-funded by Holland High Tech | TKI HSTM via the PPP Innovation Scheme (PPP-I) for public-private partnerships.