When syntax of software languages is communicated, contextfree grammars are a lingua franca. They de ne structure of syntax, but cannot express static semantics. The paper gives an overview of other successful models (attribute, two-level, parsing expression, conjunctive, Boolean grammars) in relation to de ning software languages. Author's model|grammars with contexts|can naturally express that \a valid identi er is an identi er that was declared before", and was used to dene static semantics of a small typed language. This paper discusses what prevents the practical use of the model in SLE and states open problems for further research.
is symbol x repeated n times.
begin real x x ; x x := x x ; end
| {nz } | {nz } | {nz } For this program to be valid, number n should be the same in all its three occurrences. Under certain encoding, such programs can be represented as strings of the form anbncn, for some symbols a; b; c; these strings form a well-known non-context-free language. Nevertheless, context-free grammars are capable of de ning the structure of such programs: indeed, as required by Algol's syntax, statements are separated by semicolons, there is an identi er in the left-hand side of the assignment operator, sequence of statements is framed with correctly spelled keywords begin/end, etc. Below is an example of a program that satis es these conditions.
begin real x; xx:=xxx; end This program will be considered correct despite containing undeclared identi ers.
Context-free grammars de ne structural syntax of languages, but cannot express any facts about their static semantics (what is called context conditions ). It is impossible to specify in a context-free grammar that every identi er should be declared before use, or that the number of formal parameters and actual arguments in a function call should agree. Context-sensitive grammars (initially proposed by Chomsky to describe syntax of natural languages) are powerful enough to de ne these conditions, but they are equivalent to nondeterministic linear-bounded Turing machines, in which the \nonterminal symbols", meant to represent syntactic categories, could be freely manipulated as tape symbols. No parsing algorithms with polynomial time complexity exist for such grammars1.
Subsequent research was done in two main directions: to embed \checking
actions" into rules of a context-free grammar, and to come up with an entirely
new grammatical model. The rst approach led to attribute grammars [
::=
\var" ident JsymbTable.safeAdd($1);K \;"
In this example, method safeAdd could check whether an identi er with the
same name (the name of the \current" identi er is referred to by $1) has been
declared and, if so, raise an exception. Otherwise, the new identi er is added to
the symbol table. Such essentially ad hoc techniques are still used in
industrylevel compiler compilers [
The other direction of research was to develop a reasonable (that is, e ciently
parsable) model, which would be able to specify the desired context conditions.
Of many such attempts, two-level grammars by van Wijngaarden received some
1 It is worth noting here context-sensitive parsing algorithms by Kuno [
Parsing expression grammars by Ford [
This rule matches a conditional statement in a way that the optional else clause always binds to the innermost if. Without priority of rules, the rule would lead to dangling else ambiguity.
Parsing expression grammars also provide predicates for Boolean conjunction (&) and negation (!). The following rules de ne nested comments in Pascal [20, p. 509].
A comment consists of an opening token \(*", some commented text, and a closing token \*)". This construct is non-trivial to recognize because the commented text may contain symbols \*" and \)", but not the sequence \*)". Moreover, comments may again contain comments: (* a:=b; (* comment *) *) is a correct statement. This construct can be recognized by the given rules: the idea is that CommentedText is either a complete comment or any symbol (expressed as \." in parsing expression grammars) provided that it does not start with the string \*)" (this is expressed by the negation predicate !\*)"). Similarly to negation, conjunction in parsing expression grammars is used as a mechanism of lookahead.
& BulletSymb List
These rules de ne the structure of bullet lists in Markdown. Rule for BulletList
rst veri es whether the rst element of a list starts with a bullet symbol and
only then it tries to recognize the string according to the rule for List. In the
second rule, ! BulletSymb expresses that the list cannot end at a position where
there is still a bullet symbol to be consumed.
2 Recent work on extending parsing expression grammars towards context-sensitive
parsing includes, for example, principled stateful parsing [
A systematic study of Boolean operations in grammars led to conjunctive [
& : Keyword
These rules specify in a most natural way that an identi er cannot coincide with a keyword.
Conjunctive grammars can de ne sophisticated non-context-free languages [
c wcw (w={\zamount") int amount z; if (ha}s|Bonus){ amount += 100;
| }
The main parsing algorithms for context-free grammars, including
cubictime general parsing algorithm, Earley's algorithm, recursive descent and
Generalized LR, have been extended to the case of conjunctive and Boolean
grammars [
A Boolean grammar was constructed to specify syntax and static semantics
(including scoping rules) of a programming language [
A New Life for Cross-references and Scoping
Boolean predicates & and ! in parsing expressions grammars are, in fact, positive
and negative lookahead predicates, respectively. In the rules for bullet lists in
Markdown, predicate & BulletSymb succeeds if the next symbol of the input is
a bullet, and predicate ! BulletSymb succeeds if the next symbol is not a bullet.
Neither of the predicates consume any input: they are only used to check the
lookahead symbols in the input, and those lookahead symbols can be regarded as
the right context of a string [
it was declared before it will be declared later These two informal rules state that whenever an identi er is used in a program, its declaration should appear either to its left ( ) or to its right ( ).
Consider the following fragment of a program in an assumed C-like language.
copied string wcw; with w=min z }| { : : : int f() f int ms,sec, min ; : : : return 60 * min ;g | }
extended left context (P) of u{sze of identi er min (underlined)
To ensure that identi er min used in the return statement (underlined) is
declared, one can verify whether its left context contains a function header (int
f f), keyword \int", other identi ers (ms, sec), a comma, and the declaration
of identi er min, followed by any other constructs (; . . . return 60 *), all
the way up to the use of min itself. This can be expressed in a grammar with
contexts almost verbatim [
FuncHeader \int" Identifiers CopiedString
This rule nds the substring between two positions in the input: before the
declaration of an identi er and after its use. To include the use of the identi er
into this substring, a so called extended left context P is used (that is, extended
context of an identi er is its left context concatenated with that very identi er).
After the desired substring has been found by the rule, it remains to check
whether it forms a copy language wcw (copy language can be de ned by a
conjunctive grammar [
The standard restriction that forbids redeclaration of identi ers can be now
expressed by the following rules [
It also becomes possible to distinguish between types of identi ers: the rule for a valid identi er breaks up into several rules, one for each type in the language.
The only di erence between these rules is in the keyword that should occur in the left context of an identi er use.
Because identi ers are now distinguished according to their type, it makes sense to embed type checking into a grammar with contexts.
Assignment ! ValidIntIdentifier \=" IntExpr
ValidBoolIdentifier \=" BoolExpr These rules state that a variable of a certain type can only be assigned an expression of the same type.
Syntax and static semantics of a small typed programming language has
been de ned by a grammar with contexts [
Grammars with right contexts can be used in a way similar to parsing expression grammars|as a lookahead mechanism.
The extended right context Q BulletSymb anything corresponds to the positive lookahead predicate & BulletSymb in a parsing expression grammar discussed earlier.
Several parsing algorithms, including cubic-time general parsing algorithm [
Can Grammars with Contexts Be Used in Practice?
Grammars with contexts can de ne arbitrary cross-references within a string [
Ability to de ne cross-references is what makes grammars with contexts
applicable to software languages. On a practical side, this ability is also distinctive
in parser-based language workbenches [
Variable : 'var' name=ID ';' ;
Assignment : [Variable] '=' Expression ';' ; The rst rule de nes what a variable declaration is: it is keyword var followed by an identi er and a semicolon. The identi er is to be \stored" in feature name associated with this rule3. In the second rule, [Variable] speci es a reference to an existing Variable, in particular, to its feature name (in the default setting, references are associated with the feature called name)4.
This is conceptually very similar to grammars with contexts, where ValidVariable would be used to specify the idea of what [Variable] expresses in Xtext. There is, however, an important di erence between the two approaches. To perform static checking, Xtext bases on high-level programming language code, which is either generated automatically by Xtext or is written later by a user. In contrast, grammars with contexts are purely a syntactic formalism, and after a language is de ned by a grammar, no additional code is required to further de ne its static semantics. This clearly has its advantages: a language is de ned solely by a very formal mechanism, and correctness of this de nition can be proven in a formal way.
De nition of a typed programming language by a grammar with contexts [
Can the formalism of grammars with contexts be made more
approachable? Answering this question might involve implementing an Xtext-like
language workbench based on these grammars (all necessary parsing algorithms
exist [
In the rule for DeclaredIdent, both the ordinary (ident.1) and contextual (<
. . . ident.1) occurrenes of ident have the same tag to express that these
identi ers should be identical. That is, this rule expresses that \a declared identi er
is any identi er that was declared before".
3 Xtext creates a model from a grammar using Eclipse Modeling Framework [
In a simpli ed setting, rules become classes (instances of EClass) and features of rules become elds of those classes. The model is then populated during the parsing, essentially resulting in an AST that can be further analyzed or transformed by the user. 4 The reference is made to an instance of EClass Variable; if such an instance does not exist, an error is reported. If the instance exists, the reference is associated with the value of its eld name.
Devising an adequate and convenient formalism on top of grammars with contexts is a challenging task. If this task is solved then implementing a language workbench based on these grammars would be a matter of technique.
The author is thankful to Alexander Okhotin and anonymous reviewers for their comments on earlier versions of the paper.