Eberhard Bertsch

Mark-Jan Nederhof

Sylvain Schmitz

On LR Parsing with Selective Delays

The paper investigates an extension of LR parsing that allows the delay of parsing decisions until a sufficient amount of context has been processed. We provide two characterizations for the resulting class of grammars, one based on grammar transformations, the other on the direct construction of a parser. We also report on experiments with a grammar collection.

Introduction

From a grammar engineer's standpoint, LR parsing techniques, like the LALR(1) parsers generated by yacc or GNU/bison, suffer from the troublesome existence of conflicts, which appear sooner or later in any grammar development. Tracing the source of such conflicts and refactoring the grammar to solve them is a difficult task, for which we refer the reader to the accounts of [START_REF] Malloy | Applying software engineering techniques to parser design: the development of a C# parser[END_REF] on the development of a C# grammar, and of [START_REF] Gosling | The Java TM Language Specification[END_REF] on that of the official Java grammar.

In the literature, different ways have been considered to solve conflicts automatically while maintaining a deterministic parsing algorithm-which, besides efficiency considerations, also has the considerable virtue of ruling out ambiguities-, such as unbounded regular lookaheads [START_REF] Čulik | LR-Regular grammars-an extension of LR(k) grammars[END_REF], noncanonical parsers [START_REF] Szymanski | Noncanonical extensions of bottom-up parsing techniques[END_REF], and delays before reductions [START_REF] Leermakers | Recursive ascent parsing: from Earley to Marcus[END_REF]. [START_REF] Bertsch | Some observations on LR-like parsing with delayed reduction[END_REF] have made a rather counter-intuitive observation on the latter technique: increasing delays uniformly throughout the grammar can in some cases introduce new conflicts.

In this paper we propose a parsing technique that selects how long a reduction must be delayed depending on the context. More interestingly, and unlike many techniques that extend LR parsing, we provide a characterization, using grammar transformations, of the class of grammars that can be parsed in a LR fashion with selective delays. More precisely,

• we motivate in Section 2 the interest of ML(k, m) parsing on an exerpt of the C++ grammar, before stating the first main contribution of the paper: we reformulate the technique of [START_REF] Bertsch | Some observations on LR-like parsing with delayed reduction[END_REF] as a grammar transformation, and show how selective delays can capture non-ML(k, m) grammars,

• we define the class selML(k, m) accordingly through a nondeterministic grammar transformation, which allows us to investigate its properties (Section 3),

• in Section 4 we propose an algorithm to generate parsers with selective delays, and prove that it defines the same class of grammars.

• We implemented a Java proof of concept for this algorithm (see http:// www.cs.st-andrews.ac.uk/ ~mjn/code/mlparsing/), and report in Section 5 on the empirical value of selective delays, by applying the parser on a test suite of small unambiguous grammars [START_REF] Basten | The usability of ambiguity detection methods for contextfree grammars[END_REF][START_REF] Schmitz | An experimental ambiguity detection tool[END_REF].

• We conclude with a discussion of related work, in Section 6.

Due to space constraints, many technical details, including several proofs, had to be added in the form of appendices.

Preliminaries. We assume the reader to be familiar with LR parsing, but nonetheless recall some definitions and standard notation.

A context-free grammar (CFG) is a tuple G = N, Σ, P, S where N is a finite set of nonterminal symbols, Σ a finite set of terminal symbols with N ∩ Σ = ∅together they define the vocabulary V = N Σ-, P ⊆ N × V * is a finite set of productions written as rewrite rules "A → α", and S ∈ N the start symbol. The associated derivation relation ⇒ over V * is defined as ⇒ = {(δAγ, δαγ) | A → α ∈ P }; a derivation is rightmost, denoted ⇒ rm , if γ is restricted to be in Σ * in the above definition. The language of a CFG is L(G) = {w ∈ Σ * | S ⇒ * w} = {w ∈ Σ * | S ⇒ * rm w}. We employ the usual conventions for symbols: nonterminals in N are denoted by the first few upper-case Latin letters A, B, . . . , terminals in Σ by the first few lower-case Latin letters a, b, . . . , symbols in V by the last few upper-case Latin letters X, Y , Z, sequences of terminals in Σ * by the last few lower-case Latin letters u, v, w, . . . , and mixed sequences in V * by Greek letters α, β, etc. The empty string is denoted by ε.

Given G = N, Σ, P, S , its k-extension is the grammar N {S † }, Σ {#}, P ∪ {S † → S# k }, S † where # is a fresh symbol. A grammar is LR(m) [START_REF] Knuth | On the translation of languages from left to right[END_REF][START_REF] Sippu | Parsing Theory, Vol. II: LR(k) and LL(k) Parsing[END_REF]) if it is reduced-i.e. every nonterminal is both accessible and productive-and the following conflict situation does not arise in its m-extension:

S † ⇒ * rm δAu ⇒ rm δαu = γu δ = δ or A = B or α = β S † ⇒ * rm δ Bv ⇒ rm δ βv = γwv m : u = m : wv
where "m : u" denotes the prefix of length m of u, or the whole of u if |u| ≤ m.

Marcus-Leermakers Parsing

The starting point of this paper is the formalization proposed by [START_REF] Leermakers | Recursive ascent parsing: from Earley to Marcus[END_REF] of a parsing technique due to [START_REF] Marcus | A Theory of Syntactic Recognition for Natural Language[END_REF], which tries to imitate the way humans parse natural language sentences. [START_REF] Bertsch | Some observations on LR-like parsing with delayed reduction[END_REF] have given another, equivalent, formulation, and dubbed it "ML" for Marcus-Leermakers.

The idea of uniform ML parsing is that all the reductions are delayed to take place after the recognition of a fixed number k of right context symbols, which can contain nonterminal symbols. [START_REF] Bertsch | Some observations on LR-like parsing with delayed reduction[END_REF] expanded this class by considering m further symbols of terminal lookahead, thereby defining ML(k, m) grammars. (This construction is recalled in Appendix A.) In Section 2.2, we provide yet another view on uniform ML(k, m) grammars, before motivating the use of selective delays in Section 2.3. Let us start with a concrete example taken from the C++ grammar from the 1998 standard (ISO, 1998).

C++ Qualified Identifiers

First designed as a preprocessor for C, the C++ language has evolved into a complex standard. Its rather high level of syntactic ambiguity calls for nondeterministic parsing methods, and therefore the published grammar makes no attempt to fit in the LALR(1) class.

We are interested in one particular issue with the syntax of identifier expressions, which describe a full name specifier and identifier, possibly instantiating template variables; for instance, "A::B<C::D>::E" denotes an identifier "E" with name specifier "A::B<C::D>", where the template argument of "B" is "D" with specifier "C".

The syntax of identifier expressions is given in the official C++ grammar by the following (simplified) grammar rules:

I → U | Q, U → i | T, Q → N U, N → U :: N | U ::, T → i <I>.
An identifier expression I can derive either an unqualified identifier through nonterminal U , or a qualified identifier through Q, which is qualified through a nested name specifier derived from nonterminal N , i.e. through a sequence of unqualified identifiers separated by double colons "::", before the identifier i itself. Moreover, each unqualified identifier can be a template identifier T , where the template argument, between angle brackets "<" and ">", can again be any identifier expression.

Example 1. A shift/reduce conflict appears with this set of rules. A parser fed with "A::", and seeing an identifier "B" in its lookahead window, has a nondeterministic choice between • reducing "A::" to a single N , in the hope that "B" will be the identifier qualified by "A::", as in "A::B<C::D>", and

• shifting the identifier, in the hope that "B" will be a specifier of the identifier actually qualified, for instance "E" in "A::B<C::D>::E".

An informed decision requires an exploration of the specifier starting with "B" in search of a double colon symbol. The need for unbounded lookahead occurs if "B" is the start of an arbitrarily long template identifier: this grammar is not LR(k) for any finite k.

Note that the double colon token might also appear inside a template argument. Considering that the conflict could also arise there, as after reading "A<B::" in "A<B::C<D::E>::F>::G", we see that it can be arduous to know whether a "::" symbol is significant for the resolution of the conflict or not. In fact, this is an example of a conflict that cannot be solved by using regular lookahead as proposed in [START_REF] Boullier | Contribution à la construction automatique d'analyseurs lexicographiques et syntaxiques[END_REF][START_REF] Bermudez | Practical arbitrary lookahead LR parsing[END_REF][START_REF] Farré | A bounded-connect construction for LR-Regular parsers[END_REF], because keeping track of the nesting level of well-balanced brackets is beyond the power of regular languages.1

Uniform ML

Observe that, in our extract of the C++ grammar, if we were to postpone the choice between the two possible actions and attempt to parse an N in full, then the issue would disappear. The mechanism [START_REF] Leermakers | Recursive ascent parsing: from Earley to Marcus[END_REF] employs for delaying parsing decisions is to extend a nonterminal with additional terminal and nonterminal symbols from its right context, thus delaying reduction to that nonterminal until the moment when these additional symbols have been parsed in full. This also involves introducing a new end-of-file terminal "#".

In Appendix A, we recall the ML(k, m) parser construction of [START_REF] Leermakers | Recursive ascent parsing: from Earley to Marcus[END_REF][START_REF] Bertsch | Some observations on LR-like parsing with delayed reduction[END_REF]. The automaton obtained by applying this construction on the C++ grammar is too large to be rendered on a single page. Appendix A therefore provides a simpler example. In what follows we present an alternative characterization of ML parsing on the basis of a grammar transformation.

Uniform ML as a Transformation. Although Leermakers does not present his technique in these terms, the intuition of extending nonterminals with right context can be realized by a grammar transformation that introduces nonterminals of the form [Aδ] in N = N • V ≤k , which combine a nonterminal A with its immediate right context δ.

This results for k = 1 and our C++ example into an LALR(1) grammar with rules:

[I#] → [U #] | [Q#], [I>] → [U >] | [Q>], [U #] → i # | [T #], [U >] → i > | [T >], [U ::] → i :: | [T ::], [U ] → i | [T ], [Q#] → [N U ] #, [Q>] → [N U ] >, [N U ] → [U ::] [N U ] | [U ::] [U ], [T #] → i < [I>] #, [T >] → i < [I>] >, [T ::] → i < [I>] ::, [T ] → i < [I>].
The new grammar demonstrates that our initial grammar for C++ identifier expressions is ML(1, 1): it requires contexts of length k = 1, and lookahead of length m = 1.

Combing Function. Formally, the nonterminals in N are used in the course of the application of the uniform k-combing function comb k from V * to (N Σ) * , defined recursively as:

S † → • I## I ## → • Q ## Q ## → • N U ## N U # → • U ::N U # U ::N → • i ::N U ::N → i :: • N N → • U ::N N →
comb k (α) =          [Aδ] • comb k (α ) if α = Aδα , A ∈ N, and either |δ| = k, or |δ| ≤ k and α = ε a • comb k (α ) if α = aα and a ∈ Σ ε otherwise, which is if α = ε . For instance, comb 1 (ABcDeF ) = [AB]c[De][F ].
The right parts of the rules of [Aδ] are then of the form comb k (αδ) if A → α was a rule of the original grammar, effectively delaying the reduction of α to A until after δ has been parsed.

Definition 1 (Uniform combing). Let G = N, Σ, P, S be a CFG. Its uniform k-combing is the CFG N • V ≤k , Σ, {[Aδ] → comb k (αδ) | δ ∈ V ≤k and A → α ∈ P }, [S] .
Equivalence of the Two Views. Of course we should prove that the two views on ML parsing are equivalent: Theorem 1. A grammar is ML(k, m) if and only if the uniform k-combing of its k-extension is LR(m).

Proof Idea. One can verify that the LR(m) construction on the k-combing of the k-extension of G and the ML(k, m) construction of [START_REF] Bertsch | Some observations on LR-like parsing with delayed reduction[END_REF] (recalled in Appendix A) for the same G are identical.

Selective ML

An issue spotted by [START_REF] Bertsch | Some observations on LR-like parsing with delayed reduction[END_REF] is that the classes of ML(k, m) grammars and ML(k + 1, m) grammars are not comparable: adding further delays can introduce new LR(m) conflicts in the ML(k + 1, m)-transformed grammar.

For instance, the uniform 2-combing of our grammar for C++ identifier expressions is not LR(m) for any m: Figure 1 shows the path to a conflict similar to that of the original grammar, which is therefore not uniform ML(2, m). Selective ML aims to find the appropriate delay, i.e. the appropriate amount of right context, for each item in the parser, in order to avoid such situations.

Oscillating Behaviour. Bertsch and Nederhof also show that an oscillating behaviour can occur, for instance with the grammar

S → SdA | c, A → a | ab (G odd )
being ML(k, 0) only for odd values of k, and the grammar

S → SAd | c, A → a | ab (G even )
being ML(k, 0) only for even values of k > 0, from which we can build a union grammar

S → SdA | SAd | c, A → a | ab (G 2 )
which is not ML(k, 0) for any k.

Observe however that, if we use different context lengths for the different rules of S in G 2 , i.e. if we select the different delays, we can still obtain an LR(0) grammar G 2 with rules

[S † ] → [S#]#, [S#] → [Sd][A#] | [SAd ]# | c#, [Sd] → [Sd][Ad] | [SAd ]d | cd, [SAd ] → [Sd][AAd ] | [SAd ][Ad] | c[Ad], (G 2 ) [A#] → a# | ab#, [Ad] → ad | abd, [AAd ] → a[Ad] | ab[Ad]
As we will see, this means that G 2 is selective ML with a delay of at most 2, denoted selML(2, 0). This example shows that selective ML(k, m) is not just about finding a minimal global k ≤ k such that the grammar is uniform ML(k , m). Because the amount of delay is optimized depending on the context, selective ML captures a larger class of grammars.

Selective Delays Through Grammar Transformation

We define selML(k, m) through a grammar transformation akin to that of Definition 1, but which employs a combing relation instead of the uniform kcombing function. We first introduce these relations (Section 3.1) before defining the selML(k, m) grammar class and establishing its relationships with various classes of grammars in Section 3.2 (more comparisons with related work can be found in Section 6).

Combing Relations

In the following definitions, we let G = N, Σ, P, S be a context-free grammar.

Combing relations are defined through the application of a particular inverse homomorphism throughout the rules of the grammar.

Definition 2 (Selective Combing). Grammar G = N , Σ, P , S is a selective combing of G, denoted G comb G , if there exists a homomorphism µ from V * to V * such that 1. µ(S ) = S, 2. ∀a ∈ Σ, µ(a) = a, 3. µ(N ) ⊆ N • V * , and 4. {A → µ(α ) | A → α ∈ P } = {A → αδ | A ∈ N , µ(A ) = Aδ, and A → α ∈ P }. It is a selective k-combing if furthermore µ(N ) ⊆ N • V ≤k .
We denote the elements of N by [Aδ] i , such that µ([Aδ] i ) = Aδ, with an i subscript in N to differentiate nonterminals that share the same image by µ.

Note that, if G comb G , then there exists some

k such that G is a selective k- combing of G, because µ(N ) is a finite subset of N • V * .
Another observation is that comb is transitive, and thus we can bypass any intermediate transformation by using the composition of the µ's. In fact, comb is also reflexive (using the identity on N for µ), and is thus a quasi order.

Grammar Cover. It is easy to see that a grammar and all its µ-combings are language equivalent. In fact, we can be more specific, and show that any µ-combing G = N , Σ, P , [S] 0 of G = N, Σ, P, S defines a right-to-x cover of G (see [START_REF] Nijholt | Context-free grammars: Covers, normal forms, and parsing[END_REF]), i.e. there exists a homomorphism h from P * to P * such that 1. for all w in L(G ) and right parses π of w in G , h(π ) is a parse of w in G, and 2. for all w in L(G) there is a parse π of w in G, such that there exists a right parse π of w in G with h(π ) = π.

Indeed, defining h by

h([Aδ] i → α) = A → µ(α) • δ -1 (1)
fits the requirements of a right-to-x cover.

Tree Mapping. Nevertheless, the right-to-x cover characterization is still somewhat unsatisfying, precisely because the exact derivation order x remains unknown. We solve this issue by providing a tree transformation that maps any derivation tree of G to a derivation tree of G. Besides allowing us to prove the language equivalence of G and G (see Corollary 1), this transformation also allows us to map any parse tree of G -the grammar we use for parsing-to its corresponding parse tree of G-the grammar we were interested in in the first place.

We express this transformation as a rewrite system over the set of unranked forests F(N ∪N ∪Σ) over the set of symbols N ∪N ∪Σ, defined by the abstract syntax

t ::= X(f ) (trees) f ::= ε | f • t (forests)
where "X" ranges over N ∪ N ∪ Σ and "•" denotes concatenation. Using unranked forests, our tree transformation has a very simple definition, using a rewrite system → R with one rule per nonterminal

[AX 1 • • • X r ] i in N : [AX 1 • • • X r ] i (x 0 • X 1 (x 1 ) • • • X r (x r )) → R A(x 0 ) • X 1 (x 1 ) • • • X r (x r ) (2)
with variables x 0 , x 1 , . . . , x r ranging over F(N ∪N ∪Σ). Clearly, → R is noetherian and confluent, and we can consider the mapping that associates to a derivation tree t in G its normal form t ↓ R (see Appendix B.1 for details):

Proposition 1. Let G be a CFG and G a combing of G.

1. If t is a derivation tree of G , then t ↓ R is a derivation tree of G.

2. If t is a derivation tree of G, then there exists a derivation tree t of G such that t = t ↓ R .

Since → R preserves tree yields, we obtain the language equivalence of G and G as a direct corollary of Proposition 1:

Corollary 1 (Combings Preserve Languages). Let G be a k-extended CFG and G a combing of G. Then L(G) = L(G ).

Selective ML Grammars

We define selML(k, m) grammars by analogy with the characterization proved in Theorem 1:

Definition 3 (Selective ML). A grammar is selML(k, m) if there exists a selective k-combing of its k-extension that is LR(m).
Basic Properties. We now investigate the class of selML(k, m) grammars. As a first comparison, we observe that the uniform k-combing of a grammar is by definition a selective k-combing (by setting µ as the identity on N • V ≤k ), hence the following lemma:

Lemma 1. If a grammar is ML(k, m) for some k and m, then it is selML(k, m).

As shown by G 2 , this grammar class inclusion is strict.

A second, more interesting comparison holds between selML(0, m) and LR(m). That a LR(m) grammar is selML(0, m) is immediate since comb is reflexive; the converse is not obvious at all, because a 0-combing can involve "duplicated" nonterminals, but holds nevertheless (see Appendix B.2 for details).

Lemma 2. A reduced grammar is selML(0, m) if and only if it is LR(m).

Recall that a context-free language can be generated by some LR(1) grammar if and only if it is deterministic [START_REF] Knuth | On the translation of languages from left to right[END_REF], thus selML languages also characterize deterministic languages:

Corollary 2 (Selective ML Languages). A context-free language has a selML grammar if and only if it is deterministic.

Proof. Given a selML(k, m) grammar G, we obtain an LR(m) grammar G with a deterministic language, and equivalent to G by Corollary 1. Conversely, given a deterministic language, there exists an LR(1) grammar for it, which is also selML(0,1) by Lemma 2.

Monotonicity. We should also mention that, unlike uniform ML, increasing k allows strictly more grammars to be captured by selML(k, m). Indeed, if a grammar is a selective k-combing of some grammar G, then it is also a k + 1combing using the same µ (with an extra # endmarker), and remains LR(m).

Proposition 2. If a grammar is selML(k, m) for some k and m, then it is selML(k , m ) for all k ≥ k and m ≥ m.

Strictness can be witnessed thanks to the grammar family (G k

3 ) k≥0 defined by

S → Ac k A | Bc k B , A → cA | d, B → cB | d, A → cA | a, B → cB | b (G k 3 )
where each G k 3 is selML(k + 1, 0), but not selML(k, m) for any m.

Ambiguity. As a further consequence of Proposition 1, we see that no ambiguous grammar can be selML(k, m) for any k and m.

Proposition 3. If a grammar is selML(k, m) for some k and m, then it is unambiguous.

Proof. Assume the opposite: an ambiguous grammar G has a selective k-combing G that is LR(m). Being ambiguous, G has two different derivation trees t 1 and t 2 with the same yield w. As t 1 and t 2 are in normal form for → R , the sets of derivation trees of G that rewrite into t 1 and t 2 are disjoint, and using Proposition 1 we can pick two different derivation trees t 1 and t 2 with t 1 = t 1 ↓ R and t 2 = t 2 ↓ R . As → R preserves tree yields, both t 1 and t 2 share the same yield w, which shows that G is also ambiguous, in contradiction with G being LR(m) and thus unambiguous.

Again, this grammar class inclusion is strict, because the following unambiguous grammar for even palindromes is not selML(k, m) for any k or m, since its language is not deterministic:

S → aSa | bSb | ε (G 4 )
Undecidability. Let us first refine the connection between selML and LR in the case of linear grammars: recall that a CFG is linear if the right-hand side of each one of its productions contains at most one nonterminal symbol. A consequence is that right contexts in linear CFGs are exclusively composed of terminal symbols. In such a case, the selML(k, m) and LR(k + m) conditions coincide (see Appendix B.2 for details):

Lemma 3. Let G be a reduced linear grammar, and k and m two natural integers. Then G is selML(k, m) if and only if it is LR(k + m).

Note that in the non-linear case, the classes of selML(k, m) and LR(k+m) grammars are incomparable. Nevertheless, we obtain as a consequence of Lemma 3:

Theorem 2. It is undecidable whether an arbitrary (linear) context-free grammar is selML(k, m) for some k and m, even if we fix either k or m.

Proof. [START_REF] Knuth | On the translation of languages from left to right[END_REF] has proven that it is undecidable whether an arbitrary linear context-free grammar is LR(n) for some n.

Parser Construction

This section discusses how to directly construct an LR-type parser for a given grammar and fixed k and m values. The algorithm is incremental, in that it attempts to use as little right context as possible: this is interesting for efficiency reasons (much as incremental lookaheads in [START_REF] Ancona | Efficient construction of LR(k) states and tables[END_REF][START_REF] Parr | LL and LR translators need k > 1 lookahead[END_REF]), and actually needed since more context does not necessarily lead to determinism (recall Section 2.3). The class of grammars for which the algorithm terminates successfully (i.e. results in a deterministic parser, without ever reaching a failure state) coincides with the class of selML(k, m) grammars (see propositions 4 and 5). An extended example of the construction will be given in Section 4.2.

Algorithm

Algorithm 1 presents the construction of an automaton from the k-extension of a grammar. We will call this the selML(k, m) automaton. In the final stages of the construction, the automaton will resemble an LR(m) automaton for a selective k-combing. Before that, states are initially constructed without right context. Right contexts are extended only where required to solve conflicts. States are represented as sets of items. Each such set q is associated with three more sets of items. The first is its closure close(q). The second is conflict(q), which is the set of closure items that lead to a shift/reduce or reduce/reduce conflict with another item, either immediately in q or in a state reachable from q by a sequence of transitions. A conflict item signals that the closure step that predicted the corresponding rule, in the form of a non-kernel item, must be reapplied, but now from a nonterminal [Bβ] with longer right context β. Lastly, the set deprecate(q) contains items that are to be ignored for the purpose of computing the Goto function.

Item Closure. The sets close(q), conflict(q) and deprecate(q) are initially computed from the kernel q alone. However, subsequent visits to states reachable from q may lead to new items being added to conflict(q) and then to close(q) and deprecate(q). How items in these three sets are derived from one another for given q is presented as the deduction system in Figure 2.

The closure step is performed as in conventional LR parsing, except that right context is copied to the right-hand side of a predicted rule. The conflict detection step introduces a conflict item, after a shift/reduce or reduce/reduce conflict appears among the derived items in the closure. Conflict items solicit additional right context, which Algorithm 1: Construction of the selML(k, m) automaton for the k-extension of G = N, Σ, P, S , followed by construction of a selective k-combing.

1: States ← ∅ 2: Transitions ← ∅ 3: Agenda ← ∅ 4: qinit = {(S † → • S# k , {ε})} 5: NewState(qinit) 6: while Agenda = ∅ do 7: q ← pop(Agenda) 8:
remove (q, X, q ) from Transitions for any X and q 9: apply Figure 2 to add new elements to the three sets associated with q 10: for all

([Aδ] → αX • β, L) ∈ conflict(q) do 11:
for all q such that (q , X, q) ∈ Transitions do

if there are no ([Aδ] → αX • β, L) ∈ conflict(q) then 16: qmax ← close(q) \ deprecate(q) 17:
for all X such that there is (

[Aδ] → α • Xβ, L) ∈ qmax do 18: q ← Goto(qmax, X) 19: if q /
∈ States then 20:

NewState(q )

21:

else 22: for all ([A δ ] → α X • β , L) ∈ conflict(q ) do 23: AddConflict(([A δ ] → α • Xµ(β ), L), q) 24:
end for 25:

end if

26:

Transitions ← Transitions ∪{(q, X, q )} 27:

end for 28:

end if 29: end while 30: construct a selective k-combing as explained in the running text 31: 32: function NewState(q) 33: close(q) ← q 34: conflict(q) ← ∅

35:

deprecate(q) ← ∅

36:

States ← States ∪{q} 37:

Agenda ← Agenda ∪{q} 38: end function 39:

40: function AddConflict(([Aδ] → α • Xβ, L), q) 41: if ([Aδ] → α • Xβ, L) / ∈ conflict(q) then 42: conflict(q) ← conflict(q) ∪ {([Aδ] → α • Xβ, L)} 43:
Agenda ← Agenda ∪{q} 44:

end if 45: end function

([Aδ] → α • [Bβ 1 ]β 2 , L) ∈ close(q) ([Bβ 1 ] → • γβ 1 , L ) ∈ close(q) B → γ ∈ P, L = First m (β 2 L) (closure) ([A 1 δ 1 ] → α 1 • β 1 , L 1 ) ∈ close(q) ([A 2 δ 2 ] → α 2 •, L 2 ) ∈ close(q) ([A 2 δ 2 ] → α 2 •, L 2 ) ∈ conflict(q) (A 1 δ 1 , α 1 , β 1 ) = (A 2 δ 2 , α 2 , ε), First m (µ(β 1 )L 1 ) ∩ L 2 = ∅ (conflict detection) ([Aδ] → α • [Bβ], L) ∈ close(q) ([Bβ] → • γ, L) ∈ conflict(q) ([Aδ] → α • [Bβ], L) ∈ conflict(q) (conflict propagation) ([Aδ] → α • [Bβ 1 ]Xβ 2 , L) ∈ close(q) ([Bβ 1 ] → • γ, L ) ∈ conflict(q) ([Aδ] → α • [Bβ 1 X]β 2 , L) ∈ close(q) |β 1 | < k, L = First m (Xβ 2 L), (extension)
([Bβ] → • γ, L) ∈ conflict(q) ⊥ |β| = k (failure) ([Aδ] → α • [Bβ 1 X]β 2 , L) ∈ close(q) ([Aδ] → α • [Bβ 1 ]Xβ 2 , L) ∈ deprecate(q) (deprecation) ([Aδ] → α • [Bβ 1 X]β 2 , L) ∈ close(q) ([Bβ 1 ] → • γ , L ) ∈ deprecate(q) B → γ ∈ P, µ(γ ) = γβ 1 , L = First m (Xβ 2 L), ( deprecate closure)
Figure 2: Closure of set q with local resolution of conflicts.

• may be available locally in the current state, as in step extension, where nonterminal [Bβ 1 ] is extended to incorporate the following symbol X-we assume µ here is a generic "uncombing" homomorphism, turning a single nonterminal [Bβ 1 ] into a string Bβ 1 ∈ N • V ≤k -, or

• if no more right context is available at the closure item from which a conflict item was derived, then the closure item itself becomes a conflict item, by step conflict propagation-propagation of conflicts across states is realized by Algorithm 1 and will be discussed further below-, or

• if there is ever a need for right context exceeding length k, then the grammar cannot be selML(k, m) and the algorithm terminates reporting failure by step failure.

Step deprecation expresses that an item with shorter right context is to be ignored for the purpose of computing the Goto function. The Goto function will be discussed further below. Similarly, step deprecate closure expresses that all items predicted from the item with shorter right context are to be ignored.

Main Algorithm. Initially, the agenda contains only the initial state, which is added in line 5. Line 7 of the algorithm removes an arbitrary element from the agenda and assigns it to variable q. At that point, either close(q) = q and conflict(q) = deprecate(q) = ∅ if q was not considered by line 7 before, or elements may have been added to conflict(q) since the last such consideration, which also requires updating of close(q) and deprecate(q), by Figure 2. By a change of the latter two sets, also the outgoing transitions may change. To keep the presentation simple, we assume that all outgoing transitions are first removed (on line 8) and then recomputed. From line 10, conflicting items are propagated to states immediately preceding the current state, by one transition. Such a preceding state is then put on the agenda so that it will be revisited later.

Outgoing transitions are (re-)computed from line 15 onward. This is only done if no conflicting items had to be propagated to preceding states. Such conflict items would imply that q itself will not be reachable from the initial state in the final automaton, and in that case there would be no benefit in constructing outgoing transitions from q.

For the purpose of applying the Goto function, we are only interested in the closure items that have maximal right context, as all items with shorter context were found to lead to conflicts. This is the reason why we take the set difference q max = close(q) \ deprecate(q). The Goto function is defined much as usual:

Goto(q max , X) = {([Aδ] → αX • β, L) | ([Aδ] → α • Xβ, L) ∈ q max } . (3)
The loop from line 22 is very similar to that from line 10. In both cases, conflicting items are propagated from a state q 2 to a state q 1 along a transition (q 1 , X, q 2 ). The difference lies in whether q 1 or q 2 is the currently popped element q in line 7. The propagation must be allowed to happen in both ways, as it cannot be guaranteed that no new transitions are found leading to states at which conflicts have previously been processed.

Combing Construction. After the agenda in Algorithm 1 becomes empty, only those states reachable from the initial state q init via transitions in Transitions are relevant, and the remaining ones can be removed from States. From the reachable states, we can then construct a selective k-combing, with start symbol S † , as follows.

For each q n ∈ States and (

[Aδ] → X 1 • • • X n •, L) ∈ close(q n ) \ deprecate(q n
), some n ≥ 0, find each choice of:

• q 0 , . . . , q n-1 ,

• β 0 , . . . , β n , with β n = ε, such that for 0 ≤ j < n,

• (q j , X j+1 , q j+1 ) ∈ Transitions,

• ([Aδ] → X 1 • • • X j • X j+1 β j+1 , L) ∈ close(q j ) \ deprecate(q j )
, and

• β j = µ(X j+1 )β j+1 .
It can be easily seen that β 0 must be of the form αδ, for some rule A → α. For each choice of the above, now create a rule

Y 0 → Y 1 • • • Y n ,
where Y 0 stands for the triple (q 0 , Aδ, L), and for 1 ≤ j ≤ n:

• if X j is a terminal then Y j = X j , and
• if X j is of the form [B j γ j ] then Y j stands for the triple (q j-1 , B j γ j , L j ),

where

L j = First m (β j L).
We assume here that µ(Y 0 ) = Aδ and µ(Y j ) = B j γ j for 1 ≤ j ≤ n.

Example

Example 2. Let us apply Algorithm 1 to the construction of a selML(2, 0) parser for G odd . The initial state is q init = {S † → •S##} (there is no lookahead set since we set m = 0) and produces through the rules of Figure 2 close

(q init ) = {S † → •S##, S → •SdA, S → •c} . (4)
Fast-forwarding a little, the construction eventually reaches state

q Sd = {S → Sd • A} with close(q Sd ) = {S → Sd • A, A → •a, A → •ab} , (5)
which in turn reaches state

q Sda = {A → a•, A → a • b} with close(q Sda ) = q Sda , (6) conflict(q Sda ) = {A → a•} . (7)
As this item is marked as a conflict item, line 10 of Algorithm 1 sets

conflict(q Sd ) = {A → •a} , (8)
and puts q Sd back in the agenda. Then, the conflict propagation rule is fired to set

conflict(q Sd ) = {A → •a, S → Sd • A} , (9)
and by successive backward propagation steps we get

conflict(q init ) = {S → •SdA} . (10)
The extension rule then yields

close(q init ) = {S † → •S##, S → •SdA, S → •c, S † → •[S#]#, S → •[Sd]A} , (11)
which is closed to obtain

close(q init ) = {S † → •S##, S → •SdA, S → •c, S † → •[S#]#, S → •[Sd]A, [S#] → •SdA#, [S#] → •c#, [Sd] → •SdAd , [Sd] → •cd} , (12)
and we can apply again the extension rule with the conflicting item S → •SdA:

close(q init ) = {S † → •S##, S → •SdA, S → •c, S † → •[S#]#, S → •[Sd]A, [S#] → •SdA#, [S#] → •c#, [Sd] → •SdAd , [Sd] → •cd, [S#] → •[Sd]A#, [Sd] → •[Sd]Ad} . (13)
The deprecate and deprecate closure rules then yield

deprecate(q) = {S † → •S##, S → •SdA, S → •c, [S#] → •SdA#, [Sd] → •SdAd , . . .} . (14)
We leave the following steps to the reader; the resulting parser is displayed in Figure 3 (showing only items in close(q) \ deprecate(q) in states).

Correctness

First observe that Algorithm 1 always terminates: the number of possible sets q, along with the growing sets close(q), conflict(q) and deprecate(q), is bounded. Termination by the failure step of Figure 2 occurs only when we know that the resulting parser cannot be deterministic; conversely, successful termination means that a deterministic parser has been constructed. One could easily modify the construction to keep running in case of failure and output a nondeterministic parser instead, for instance to use a generalized LR parsing algorithm on the obtained parser.

The correctness of the construction follows from propositions 4 and 5 (see Appendix C for details).

Proposition 4. If Algorithm 1 terminates successfully, then the constructed grammar is a selective k-combing. Furthermore, this combing is LR(m).

Proof Idea. The structure of the selML(k, m) automaton and the item sets ensure that the constructed grammar satisfies all the requirements of a selective k-combing. Had this been non-LR(m), then there would have been further steps or failure.

Proposition 5. If the grammar is selML(k, m), then the algorithm terminates successfully.

Proof Idea. The selML(k, m) automaton under construction reflects minimum right context for nonterminal occurrences in any selective k-combing with the LR(m) property. Furthermore, failure would imply that right context of length exceeding k is needed.

As a consequence, we can refine the statement of Theorem 2 with Corollary 3. It is decidable whether an arbitrary context-free grammar is selML(k, m), for given k and m.

Experimental Results

We have implemented a proof of concept of Algorithm 1, which can be downloaded from http://www.cs.st-andrews.ac.uk/ ~mjn/code/mlparsing/. Its purpose is not to build actual parsers for programming languages, but merely to check the feasibility of the approach and compare selML with uniform ML and more classical parsers. with our test suite and the Grammar Collection. We investigated a set of small grammars that exhibit well-identified syntactic difficulties, to see whether they are treated correctly by a given parsing technique, or lie beyond its grasp. This set of grammars was compiled by [START_REF] Basten | The usability of ambiguity detection methods for contextfree grammars[END_REF] and extended in [START_REF] Schmitz | An experimental ambiguity detection tool[END_REF], containing mostly grammars for programming languages from the parsing literature and the comp.compilers archive, but also a few RNA grammars used by the bioinformatics community [START_REF] Reeder | Effective ambiguity checking in biosequence analysis[END_REF].

Conflicts. As expected, we identified a few grammars that were not LALR(1) but were selML(k, m) for small values of k and m-one may bear in mind that any progress in this respect seems worthwhile for a grammar developer struggling with conflicts.

Example 3 (Tiger). One such example is an excerpt from the Tiger syntax found at http://compilers.iecc.com/comparch/article/98-05-030. The grammar describes assignment expressions E, which are typically of the form "L := E" for L an lvalue.

E → L | L := E | i[E] of E L → i | L[E] | L.i
The grammar is not LR(m) for any m, but is ML(3, 1) and ML(2, 2): a conflict arises between inputs of the form "i[E] of E" and "i[E] := E", where the initial i should be kept as such and the parser should shift in the first case, and reduce to L in the second case. An ML(3, 1) or ML(2, 2) parser scans up to the "of" or ":=" token that resolves this conflict, across the infinite language generated by E.

Example 4 (Typed Pascal Declarations). Another example is a version of Pascal identifier declarations with type checking performed at the syntax level, which was proposed by [START_REF] Tai | Noncanonical SLR(1) grammars[END_REF]. The grammar is LR(2) and ML(1,0):

D → var IL IT ; | var RL RT ; IL → i , IL | i IT → : integer RL → i , RL | i RT → : real
On an input like "var i , i , i : real ;", a conflict arises between the reductions of the last identifier i to either an integer list IL or a real list RL with ":" as terminal lookahead. By delaying these reductions, one can identify either an integer type IT or a real type RT .

Non-Monotonicity. We found that non-monotonic behaviour with uniform ML parsers occurs more often than expected. Here is one example in addition to the C++ example given in Section 2.1; more could be found in particular with the RNA grammars of [START_REF] Reeder | Effective ambiguity checking in biosequence analysis[END_REF]. Parser Size. Because selML parsers introduce new context symbols only when required, they can be smaller than the corresponding LR or uniform ML parsers, which carry full lookahead lengths in their items-this issue has been investigated for instance by [START_REF] Ancona | Efficient construction of LR(k) states and tables[END_REF] and [START_REF] Parr | LL and LR translators need k > 1 lookahead[END_REF] for LR and LL parsers. Our results are inconclusive as to the difference of parser size (in terms of numbers of states) between selML and LR. However, selML parsers tend to be considerably smaller than uniform ML parsers. For instance, the ML(1, 1) parser for the C++ grammar fragment of Section 2.1 has 50 states, while its selML(1, 1) parser only features 28 states.

In fact, we can make the argument more formal: consider the family of grammars (G j 4 ) j>0 , each with rules:

S → A | D, A → a | Ab | Ac, D → EF j-1 F | E F j-1 F , F → a | bF, F → f | bF , E → e, E → e . (G j 4 )
The uniform ML(j, 0) parser for G j 4 has exponentially many states in j, caused by the rules [Aw] → aw for all w in {b, c} j , while the selective ML(j, 0) parser has only a linear number of states, as there is no need for delays in that part of the grammar.

Related Work

Grammar Transformations and Coverings. The idea of using grammar transformations to obtain LR(1) or even simpler grammars has been thoroughly investigated in the framework of grammar covers [START_REF] Nijholt | Context-free grammars: Covers, normal forms, and parsing[END_REF]. Among the most notable applications, [START_REF] Mickunas | Transforming LR(k) grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context grammars[END_REF] provide transformations from LR(k) grammars into much simpler classes such as simple LR(1) or (1,1)bounded right context; Soisalon-Soininen and Ukkonen (1979) transform predictive LR(k) grammars into LL(k) ones by generalizing the notion of left-corner parsing. Such techniques were often limited however to right-to-right or leftto-right covers, whereas our transformation is not confined to such a strict framework.

Parsing with Delays. A different notion of delayed reductions was already suggested by [START_REF] Knuth | On the translation of languages from left to right[END_REF] and later formalized by [START_REF] Szymanski | Noncanonical extensions of bottom-up parsing techniques[END_REF] as LR(k, t) parsing, where one of the t leftmost phrases in any rightmost derivation can be reduced using a lookahead of k symbols. The difference between the two notions of delay can be witnessed with linear grammars, which are LR(k, t) if and only if they are LR(k)-because there is always at most one phrase in a derivation-but selML(k, m) if and only if they are LR(k + m)-as shown in Lemma 3.

Like selML languages, and unlike more powerful noncanonical classes, the class of LR(k, t) grammars characterizes deterministic context-free languages. The associated parsing algorithm is quite different however from that of selML parsing: it uses the two-stacks model of noncanonical parsing, where reduced nonterminals are pushed back at the beginning of the input to serve as lookahead in reductions deeper in the stack. Comparatively, selML parsing uses the conventional LR parsing tables with a single stack.

Selectivity. Several parser construction methods attempt to use as little "information" as possible before committing to a parsing action: [START_REF] Ancona | Efficient construction of LR(k) states and tables[END_REF] and [START_REF] Parr | LL and LR translators need k > 1 lookahead[END_REF] try to use as little lookahead as possible in LR(k) or LL(k) parsing, [START_REF] Demers | Generalized left corner parsing[END_REF] generalizes left-corner parsing to delay decisions possibly as late as an LR parser, and Fortes Gálvez et al. ( 2006) propose a noncanonical parsing algorithm that explores as little right context as possible.

Concluding Remarks

Selective ML parsing offers an original balance between

• enlarging the class of admissible grammars, compared to LR parsing, while

• remaining a deterministic parsing technique, with linear-time parsing and exclusion of ambiguities,

• having a simple description as a grammar transformation, and

• allowing the concrete construction of LR parse tables.

This last point is also of interest to practitioners who have embraced general, nondeterministic parsing techniques [START_REF] Kats | Pure and declarative syntax definition: Paradise lost and regained[END_REF]: unlike noncanonical or regular-lookahead extensions, selML parsers can be used for nondeterministic parsing exactly like LR parsers. Having fewer conflicts than conventional LR parsers, they will resort less often to nondeterminism, and might be more efficient.

The following appendices contain material that will not be part of the final paper, if accepted.

A Uniform ML Parsers

We recall here the uniform ML(k, m) parser construction of [START_REF] Bertsch | Some observations on LR-like parsing with delayed reduction[END_REF]. The states are defined as sets of (k, m)-items [Aδ → β • γ, x], where A → α is a rule in P , |δ| ≤ k, αδ = βγ, and x ∈ Σ m . Define a set of items close(q), where q is a set of items, as the smallest solution of

B Grammar Transformation

B.1 Combing Relations

Remark 1 (Ranked vs. Unranked Trees). We contemplated for a while expressing the transformation performed by → R in a ranked setting, using multi bottomup tree transducers, but the apparatus felt quite heavy. In fact, one could also define combings through macro tree transductions of a very restricted form, but the list of restrictions (linear, non-erasing, order preserving, Σ-preserving, local, etc.) would be daunting.

Lemma 4. The pair (G , h) is a right-to-x cover for G.

Proof. Immediate consequence of Proposition 1 and the fact that → R preserves tree yields.

Lemma 5. The rewrite relation → R is noetherian and confluent. i

S † → • S## S ## → • SdA ## S ## → • c ## S dA → • SdA dA S dA → • c dA S † → S ## • S ## → SdA • ## S dA → SdA • dA S ## → SdA # • # S ## → SdA ## • S dA → SdA d • A A → • a A → • ab S ## → c • ## S dA → c • dA S dA → c d • A A → • a A → • ab S ## → c # • # S ## → c # • # A → a • A → a • b A → ab • S## SdA c # d # a # d # a b
Figure 4: The uniform ML(2, 0) parser for G odd .

Proof. The fact that → R is noetherian is immediate, since the number of symbols of N that appear as node labels decreases strictly at each application of → R , and since the trees we consider are finite.

Let us prove that → R is locally confluent: for all x, y, and z in F(N ∪ N ∪ Σ), x → R y and x → R z imply that there exists x ∈ F(N ∪ N ∪ Σ) such that y → * R x and z → * R x . Indeed, either y = z and we can take x = y, or the two rewrites from x have targeted two nonterminals [AX 1 . . . X q ] i and [CY 1 . . . Y r ] j in N at two different nodes of x. Observe that, in the latter case, the children of [CY 1 . . . Y r ] j labeled by Y 1 , . . . , Y r in N have not been modified by the rewrite at [AX 1 . . . X q ] i , and we can thus still rewrite at [CY 1 . . . Y r ] j in y, and symmetrically in z. Thus we can obtain a single tree x after a single rewrite step from either y or z.

We conclude by Newman's Lemma that → R is globally confluent.

Proposition 6. Let G be a CFG and G a combing of G.

1. If t is a derivation tree of G , then t ↓ R is a derivation tree of G.

2. If t is a derivation tree of G, then there exists a derivation tree t of G such that t = t ↓ R .

Proof of 1. First observe that, since → R is confluent, any strategy for ordering rewrites will lead to the same normal form t ↓ R . Here we use a bottom-up strategy, starting from the leaves (of form X(ε)) of t up to its root S (f ). We generalize the notion of derivation trees to allow any root label and not just the axiom S of the grammar. Let us prove by induction over f that Claim 4. If X(f ) is a derivation tree of G , then X(f ) ↓ R is a sequence X 0 (f 0 )X 1 (f 1 ) • • • X r (f r ) of derivation trees of G with µ(X) = X 0 X 1 • • • X r .

Figure 1 :

 1 Figure 1: Parts of the uniform ML(2, 0) parser for C++ identifier expressions.

  Items and States. The items manipulated by the algorithm are of form ([Aδ] → α • α , L), where L ⊆ Σ ≤m is a set of terminal lookahead strings, and where α and α might contain nonterminals of the form [Bβ], where B ∈ N and β ∈ V ≤k . Such nonterminals may later become nonterminals in the selective kcombing of the input grammar. To avoid notational clutter, we assume in what follows that B and [B] are represented in the same way, or equivalently, that an occurrence of B in a right-hand side is implicitly converted to [B] wherever necessary.

  Aδ] → α • Xµ(β), L), q )

Figure 3 :

 3 Figure 3: The selML(2, 0) parser for G odd .

Example 5 (

 5 Pascal Compound Statements). The following is an excerpt from ISO Pascal and defines compound statements C in terms of ";"-separated lists of statements S:C → begin L end L → L ; S | S S → ε | C This is an LALR(1)and ML(1, 0) grammar, but it is not ML(2, 0): the nonterminal [L; S] has a rule [L; S] → [L; S]; [S], giving rise to a nonterminal [S] with rules [S] → ε | [C] and a shift/reduce conflict-in fact, this argument shows more generally that the grammar is not ML(k, 0) for even k.

  close(q) = q ∪ {[B(k : γ) → • β(k : γ), y] | [δ → α • Bγ, x] ∈ close(q), B → β ∈ P, y ∈ First m ((γ : k)x)}where γ : k is the suffix of γ such that γ = (k : γ)(γ : k) and First m (α) = {m : w ∈ Σ ≤m | α ⇒ * w} for any α in V * . The reductions allowed in state q by the parser are defined asReductions(q) = {[δ → α, x] | [δ → α •, x] ∈ q} a transition by the following Goto function Goto(q, β) = close({[δ → αa • γ, x] | [δ → α • aγ, x] ∈ q and a ∈ Σ} ∪ {[δ → αBβ • γ, x] | [δ → α • Bβγ, x] ∈ q, β = k : βγ and B ∈ N })and the initial state q 0 as q 0 = close({[S † → • S# k , # m ]}) .

Figure 4

 4 Figure 4 provides an example of the Marcus-Leermakers construction on G odd . Note the conflict in the dashed state.

We can amend the rules of N to use left-recursion and solve the conflict: N → N U :: | U :: . This correction was made by the Standards Committee in

(see http: //www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#125). The correction was not motivated by this conflict but by an ambiguity issue, and the fact that the change eliminated the conflict seems to have been a fortunate coincidence. The C++ grammar of the Elsa parser(McPeak and Necula,

2004) employs right recursion.

Note that the claim implies the desired result, since a derivation tree t = S (f ) of G is then associated to a derivation tree t ↓ R = µ(S )(f 0 ) = S(f 0 ) of G (recall condition 1).

By condition 2, the case where X is a terminal symbol in Σ is immediate, and we consider the one where

By definition of a derivation tree, the forest f matches the right hand side of some production [AX 1 • • • X r ] i → α of P , which by condition 4, verifies µ(α ) = αX 1 • • • X r for some A → α in P . Write α = Y 1 • • • Y m ; by induction hypothesis on f and the fact that (f

is a sequence of derivation trees of G. Then

is indeed a sequence of derivation trees of G.

Proof of 2. The idea is to revert the computation exhibited for the proof of item 1 to build a tree t :

Item 2 then follows from condition 1, since a derivation tree t of G is a sequence S(f ) with µ(S ) = S, for which Claim 5 yields the existence of a derivation tree t = S(f ) with t ↓ R = t.

We prove the claim by induction on f . Again, the case where X 0 is a terminal in Σ is trivial, since then r = 0 and f 0 = ε, and setting X = X 0 fits the statement of Claim 5 by condition 2.

Let us therefore consider the case where X 0 is a nonterminal in N . Then f 0 has to match the right hand side of some production X 0 → α in P , and by condition 4 there exists a corresponding production

Applying the induction hypothesis on each factor yields the existence of derivation trees

as desired.

B.2 Selective ML Grammars

Lemma 6. A reduced grammar is selML(0, m) if and only if it is LR(m).

Proof. First observe that, if a grammar is LR(m), then it is also selML(0, m) if we take N = N and the identity for µ.

iii Conversely, let us prove that if G is not LR(m), then it is not selML(0, m). Consider for this a 0-combing G of the 0-extension of G, and a conflict in the m-extension of G:

Because G is reduced, there exists a derivation

for some w . We obtain in the m-extension of G

Observe that this is an LR(m) conflict situation in G if γ 1 = γ 2 ; assuming the contrary, we can write γ 1 = γ C 1 γ 1 and γ 2 = γ C 2 γ 2 where γ is the longest common prefix of γ 1 and γ 2 , and

where w is the corresponding suffix of w from (18). Because m : w u = m : w wv, this is an LR(m) conflict in G if ρ 1 = ρ 2 . Otherwise, we can again pick the longest common prefix of ρ 1 and ρ 2 and keep unfolding the derivation in (18); as the latter is finite, this process eventually terminates and allows to exhibit a conflict.

Lemma 7. Let G be a reduced linear grammar, and k and m two natural integers. Then G is selML(k, m) if and only if it is LR(k + m).

where Follow k (A) = {k : w ∈ Σ ≤k | S ⇒ * rm δAw} and µ([Au]) = Au as usual, and

the only problematic case in order to exhibit an LR(k + m) conflict is that of Proof of selML(k, m) implies LR(k + m). Assume G is not LR(k +m); then we have a conflict in its (k + m)-extension:

Consider now any k-combing G of the k-extension of G; the following situation occurs in the m-extension of G :

If X or Y is in Σ, then both are, and u 1 αv 1 = γw 1 v 1 and u 2 βv 2 = γv 2 w 2 v 2 allow to exhibit an LR(m) conflict in G : since |w 1 | ≤ k, we can rewrite γv 2 w 2 v 2 as γw 2 w 2 such that γw 2 = γw 1 , and we have m :

Otherwise, X = Y but the combing might associate two different nonterminals X and Y of N to them (or if they are the same nonterminal we immediately obtain an LR(m) conflict as in the terminal case). However, applying the same reasoning as in the proof of Lemma 2, because G is reduced, we will eventually reach a case where a conflict arises.

C Parser Construction

Proposition 7. If Algorithm 1 terminates successfully (i.e. without the failure step being triggered), then the constructed grammar is a selective k-combing. Furthermore, this combing is LR(m).

Proof. In order to prove that the grammar is a selective combing it suffices to show that: v • S † is a nonterminal in the grammar, and

• for every nonterminal [Aδ] i in the grammar and each rule A → α ∈ P ∪ {S † → S# k }, there is exactly one rule [Aδ] i → β with µ(β) = αδ.

A central observation is that if the set close(q 0 ) \ deprecate(q 0 ) of a reachable state q 0 contains an item ([Bδ ] → γ 1 • [Aδ]γ 2 , L ), and A → α ∈ P , then there is precisely one choice of:

• q 1 , . . . , q n ,

• X 1 , . . . , X n ,

• β 0 , . . . , β n , with β 0 = αδ and β n = ε, such that for 0 ≤ j < n,

• (q j , X j+1 , q j+1 ) ∈ Transitions,

∈ close(q j ) \ deprecate(q j ), and

This follows from the rules in Figure 2 and the definition of the Goto function.

In particular, where a closure item with longer right context is added, the corresponding item with shorter right context is deprecated.

In terms of the selective combing, the above implies that for every nonterminal [Aδ] i and rule A → α (excepting S † → S# k for now) there must be exactly one rule [Aδ] i → β with µ(β) = αδ. The special case of S † → S# k can be treated similarly.

That the grammar is a selective k-combing follows from the fact that the inference rules in Figure 2 do not allow right context longer than k.

In order to prove that the combing is LR(m), we first show that for each state of the LR(m) automaton for the combing there is a corresponding state q of the selML(k, m) automaton. Where the LR(m) state has an item

This can be proven by induction, starting at the initial state.

Next, it can be shown that if there were a conflict in an LR(m) state, then a similar conflict had arisen in a corresponding selML(k, m) state, and this had triggered further restructuring of the automaton before termination of the algorithm, leading to a contradiction. Proposition 8. If the grammar is selML(k, m), then the algorithm terminates successfully.

Proof. We rely on the following invariant of Algorithm 1. For each state q reachable through n transitions (q 0 , X 1 , q 1 ), . . . , (q n-1 , X n , q n ) ∈ Transitions with q 0 = q init and q n = q, and for each item ([Aδ] → α • [Bβ 1 X]β 2 , L) ∈ vi close(q), any combing for the k-extension of the input grammar that is LR(m) cannot allow:

where As long as no right context has been extended (step 'extension' in Figure 2), the above invariant holds trivially. That the invariant is preserved by steps extending right context follows from the observation that a conflict detected in the selML(k, m) automaton implies a corresponding conflict in the LR(m) automaton.

In more detail, the 'conflict detection' step from Figure 2 is triggered by the presence of:

Let q be reachable through n transitions (q 0 , X 1 , q 1 ), . . . , (q n-1 , X n , q n ) ∈ Transitions with q 0 = q init and q n = q. In a combing with right contexts of similar length, we would have:

where β 1 ⇒ * rm w for some w with m : wu = m : v ∈ First m (µ(β 1 )L 1 ) ∩ L 2 and µ(γ 3 ) = µ(X 1 • • • X n ). (Recall that we use subscripts such as i 1 and i 2 to differentiate nonterminals of a combing that share the same image by µ, as motivated in Section 3.) This implies a LR(m) conflict. Note that if one constructs a combing with extended right context for the occurrence of A 1 only, such that we have:

with µ(γ 1 ) = µ(γ 1 ), µ(γ 2 ) = µ(γ 2 ), and m : u ∈ First m (δ 3 u ), then the conflict is still present. Therefore, any combing that is LR(m) must at least have extended right context for A 2 , given left context and lookahead as above. Extension of right context δ 2 , by at least one more symbol X to become δ 2 X, is achieved by the interaction of the inference rules (in particular steps 'extension' and 'conflict propagation') and the propagation of conflict items across states. It follows that if an item ([Bβ] → • γ, L) ∈ conflict(q) occurs with |β| = k, then there is a LR(m) conflict that cannot be resolved with a k-combing, and the grammar cannot be selML(k, m). vii


Alexander Afriat 2013 Weyl'

Alexander Afriat

Weyl's gauge argument

Introduction

Weyl's first gauge theory (1918) was a generalisation of Einstein's general relativity; his second gauge theory, 1 which grew out of the first, remained a relativistic theory of curved spacetime, but with a matter field of two-spinors subject to Weyl's version of the Dirac equation. The proper orthochronous Lorentz group SO + (1, 3) changes neither the length, origin, spatial parity, nor temporal orientation of spacetime fourvectors, whose parallel propagation is accordingly governed in Weyl's second theory by a connection A = A a µ dx µ ⊗ T a with values in the Lie algebra o(1, 3) = Lie SO + (1, 3). The parallel transport of Weyl's two-spinors, which are subject to a group we can call 2 W(2, C) = {g ∈ GL(2, C) : |detg| = 1}, is given by a connection A with values in w(2, C) = Lie W(2, C); the homomorphism h : W(2, C) → SO + (1, 3) is therefore at the core of Weyl's theory. We'll see how he exploits the angular freedom e iλ left by h for "the critical part of the theory": 3 the derivation of electromagnetism.

The standard "gauge principle" or "gauge argument" is sometimes attributed to Weyl. 4 Not only is his argument quite different, but it avoids the exact connection A = dλ and vanishing field F = d 2 λ that vitiate the standard argument.

1 Weyl (1929a,b,c). See [START_REF] Straumann | Zum Ursprung der Eichtheorien bei Hermann Weyl[END_REF], [START_REF] O'raifeartaigh | The dawning of gauge theory[END_REF]), O'Raifeartaigh & Straumann (2000), [START_REF] Brading | Which symmetry? Weyl, and the conservation of electric charge[END_REF] and [START_REF] Sakurai | Local spinor structures in V. Fock's and H. Weyl's work on the Dirac equation[END_REF] for more recent accounts.

2 It is sometimes known as Spin C ; see [START_REF] Friedrich | Dirac operators in Riemannian geometry[END_REF] §1.6 for instance.

3 Weyl (1929b) p. 348: " §6. E l e k t r i s c h e s F e l d. Wir kommen jetzt zu dem kritischen Teil der Theorie. Meiner Meinung nach liegt der Ursprung und die Notwendigkeit des elektromagnetischen Feldes in folgendem begründet." 4 Brading (2002) pp. 3-4, Healey (2007) p. 160 for instance.

1

2 The standard gauge argument

One begins with a free field, of two-spinors ψ ∈ C 2 for instance. The Lagrangian

L = ψ / ∂ ψ is invariant under the global transformation (1) ψ → e iκ ψ,
where "global" means that κ is the same everywhere; / ∂ stands for the sum σ µ ∂ µ , in which σ 0 is the identity and σ k the three Pauli operators. It is then argued 5 that L should also be invariant under the local transformation

(2) ψ → ψ λ = e iλ ψ,
where λ : M → R is a smooth function on the base manifold M .

Most immediately what are we to make of the initial, central demand of local gauge invariance? The demand is anything but self-evident and presumably, in the context of the gauge argument, must be argued for on some basis. Unlike the global invariance, the demand for the corresponding local invariance does not have an immediate physical counterpart. Is it to be taken as a direct implementation of some sort of unassailable first principle? If so, is the demand (or principle) something with which we are already familiar only in a different form? A common justification for the demand of local gauge invariance in presenting the gauge argument is to present it as some sort of "locality" requirement. In outline, the "gauge locality argument" is that global gauge invariance is somehow at odds with the idea of a local field theory, and that to remedy this we must instead require local gauge invariance. This rather brief argument is just how Yang and Mills motivated the demand in their seminal 1954 paper,6 very much setting the tone for subsequent treatments. Just what to make of this argument is not clear, however, there are many interrelated senses of locality that might be at issue. (Martin, 2002, p. S225) 5 [START_REF] Göckeler | Differential geometry, gauge theories, and gravity[END_REF] p. 48: "In physical terms we may interpret the requirement of local gauge invariance (independence of the fields at different spacetime points) as expressing the absence of (instantaneous) action at a distance." [START_REF] Ryder | Quantum field theory[END_REF] p. 93: "So when we perform a rotation in the internal space of ϕ at one point, through an angle Λ, we must perform the same rotation at all other points at the same time. If we take this physical interpretation seriously, we see that it is impossible to fulfil, since it contradicts the letter and spirit of relativity, according to which there must be a minimum time delay equal to the time of light travel. To get round this problem we simply abandon the requirement that Λ is a constant, and write it as an arbitrary function of space-time, Λ(x µ ). This is called a 'local' gauge transformation, since it clearly differs from point to point." [START_REF] Teller | The gauge argument[END_REF] p. S469: "why should we expect invariance under a local phase transformation to begin with? The plausibility of such invariance probably arises with a misleading analogy with global phase transformations which can be imposed on individual state functions with no change of description." See also [START_REF] Sakurai | Local spinor structures in V. Fock's and H. Weyl's work on the Dirac equation[END_REF] p. 16, [START_REF] Aitchison | Gauge theories in particle physics[END_REF]) p. 176, Mandl & Shaw (1984) p. 263, [START_REF] Ramond | Field theory: a modern primer[END_REF]) pp. 183-91, O'Raifeartaigh (1997) p. 118. One is reminded of Weyl's rejection (1929a, p. 331;1929b, p. 286) of distant parallelism.

At any rate, as things stand the Lagrangian

L λ = ψλ / ∂ ψ λ = ψe -iλ σ µ ∂ µ (e iλ ψ) = ψσ µ (∂ µ + i∂ µ λ)ψ
is not invariant since the derivative ∂ µ has become ∂ µ +i∂ µ λ. To offset (2) we therefore have to subtract the term i∂ µ λ that alters L , yielding the covariant differential

D = d- idλ with components D µ = ∂ µ -i∂ µ λ. Writing / D = σ µ D µ , the balanced Lagrangian L ′ = ψλ /
Dψ λ will be equal to L for all λ. Another way of seeing that differentiation has to be balanced by dλ to offset (2): The momentum operator P becomes -id in the position representation; applied to ψ λ it gives -idψ λ = e iλ (-id + dλ)ψ λ , in other words U P U † U ψ = P λ ψ λ , the position representation of the rotated momentum operator P λ being -id + dλ. 7 It is then argued that an interaction F = dA = d 2 λ is thereby deduced, 8 whose potential A is dλ. But since d 2 vanishes the interaction does too, as has often been pointed out. 9 The gauge argument is fertile enough to produce another two Lagrangians, 10

L A = j ∧ A = j µ A µ = ψσ µ A µ ψ and L F = F ∧ * F = - 1 4 F µν F µν ,
where the current density three-form

j = 1 3! ε µνστ j µ dx ν ∧ dx σ ∧ dx τ
corresponds to the vector with components j µ = ψσ µ ψ. One can either leave

A = dλ in L ′ to offset (2), or balance L λ with L A in the sum L ′ = L λ + L A . Again, a
Lagrangian L F derived from the gauge argument will vanish. But once the argument has produced the exact potential A = dλ and vanishing interaction F = dA = d 2 λ

7 My analysis owes much to [START_REF] Lyre | The principles of gauging[END_REF][START_REF] Lyre | Lokale Symmetrien und Wirklichkeit: eine Naturphilosophische Studie über Eichtheorien und Strukturenrealismus[END_REF]Lyre ( , 2004a,b),b). But

ϕ|P |ϕ = ϕU |U P U † |U ϕ = ϕU |P |U ϕ
seems relevant to his claim (2004b, pp. 649-51) that local phase transformations are not observable. I would say they are-unless one compensates to restore invariance. P. 651 he writes that: "local phase transformations are already unmasked as not observable. From this insight, however, the whole logic of the received view breaks down. Since the introduction of an interaction field as intended by the received view seemingly changes physics (those fields are even directly observable themselves), it is necesary from this view to consider local gauge transformations as changing physics as well in order to tell the story about compensation. 9 Auyang (1995) p. 58, [START_REF] Brown | Aspects of objectivity in quantum mechanics[END_REF]) pp. 50-3, Teller (2000) pp. S468-9, [START_REF] Lyre | The principles of gauging[END_REF][START_REF] Lyre | Lokale Symmetrien und Wirklichkeit: eine Naturphilosophische Studie über Eichtheorien und Strukturenrealismus[END_REF]Lyre ( , 2004a,b),b), [START_REF] Healey | On the reality of gauge potentials[END_REF] p. 438, [START_REF] Martin | Gauge principles, gauge arguments and the logic of nature[END_REF] p. S229, [START_REF] Martin | On continuous symmetries and the foundations of modern physics[END_REF]) p. 45, Catren (2008) pp. 512, 520. But the general structure of the covariant derivative is about right; [START_REF] Lyre | Lokale Symmetrien und Wirklichkeit: eine Naturphilosophische Studie über Eichtheorien und Strukturenrealismus[END_REF] p. 84: "Denn wenngleich das Eichprinzip [ . . . ] nicht zwingend auf nichtflache Konnektionen führt, so ist ja doch die in der kovarianten Ableitung vorgegebene Struktur des Wechselwirkungterms auch für den empirisch bedeutsamen Fall nichtverschwindender Feldstärken korrekt beschrieben. Diese Wechselwirkungsstruktur is also tatsächlich aus der lokalen Eichsymmetrie-Forderung hergeleitet."

10 Cf. Weyl (1929c) p. 283.

one can perhaps claim that A is no longer exact. The exact term dλ would then be subtracted from one that isn't 11 in the gauge transformation

(3)

A → A ′ = A -dλ.
The total Lagrangian L ′ + L F is indifferent to (2) and (3).

Weyl's argument

As pointed out in the Introduction, Weyl's two-spinors are subject to a group 12 W(2, C) slightly larger than SL(2, C) = {g ∈ GL(2, C) : det g = 1}. To produce electromagnetism Weyl uses the U(1) freedom expressed by ( 4)

h(e iλ g) = h(g) ∈ SO + (1, 3), g ∈ W(2, C). 13 SO + (1, 3) = G and W(2, C) = G ′
are just 'structure' groups, acting at a generic spacetime point. What about the corresponding gauge groups G , G ′ acting on all of spacetime M ? In special relativity "there's just a single tetrad"; so there's just one

SO + (1, 3) = G = G , one W(2, C) = G ′ = G ′ ,
and above all one e iλ . 14 But with spacetime curvature the tetrad varies, 15 and so does λ. This could mean the following: 16 Only a o(1, 3)-valued connection A allows the assignment of the same tetrad to distant points-only with flatness can there be global constancy or 'sameness.' With curvature it becomes meaningless to say that tetrads at distant points are the same. 11 One can wonder what the gauge argument is for if the inexact potential A was already there to begin with. The exact term subtracted in (3) has more to do with the invariance of F = dA = dA ′ than with the gauge argument.

12 Weyl (1929b) p. 333: "man beschränke sich auf solche lineare Transformationen U von ψ 1 , ψ 2 , deren Determinante den absoluten Betrag 1 hat." 13 Weyl (1929c) p. 291: "It is my firm conviction that we must seek the origin of the electromagnetic field in another direction. We have already mentioned that it is impossible to connect the transformations of the ψ in a unique manner with the rotations of the axis system; however we may attempt to accomplish this by means of invariants which can be used as constituents of an action quantity we always find that there remains an arbitrary "gauge factor" e iλ . Hence the local axis-system does not determine the components of ψ uniquely, but only within such a factor of absolute magnitude 1." Weyl (1931) p. 195: "Aus der Natur, dem Transformationsgesetz der Größe ψ ergibt sich, daß die vier Komponenten ψ̺ relativ zum lokalen Achsenkreuz nur bis auf einen gemeinsamen Proportionalitätsfaktor e iλ durch den physikalischen Zustand bestimmt sind, dessen Exponent λ willkürlich vom Orte in Raum und Zeit abhängt, und daß infolgedessen zur eindeutigen Festlegung des kovarianten Differentials von ψ eine Linearform α fαdxα erforderlich ist, die so mit dem Eichfaktor in ψ gekoppelt ist, wie es das Prinzip der Eichinvarianz verlangt."

14 Weyl (1929b) p. 348: "In der speziellen Relativitätstheorie muß man diesen Eichfaktor als eine Konstante ansehen, weil wir hier ein einziges, nicht an einen Punkt gebundes Achsenkreuz haben." Weyl (1929c) p. 291: "In the special theory of relativity, in which the axis system is not tied up to any particular point, this factor is a constant." 15 The gauge groups become infinite-dimensional. Weyl (1929b) p. 348: "Anders in der allgemeinen Relativitätstheorie: jeder Punkt hat sein eigenes Achsenkreuz und darum auch seinen eigenen willkürlichen Eichfaktor; dadurch, daß man die starre Bindung der Achsenkreuze in verschiedenen Punkten aufhebt, wird der Eichfaktor notwendig zu einer willkürlichen Ortsfunktion." Weyl (1929c) p. 291: "But it is otherwise in the general theory of relativity when we remove the restriction binding the local axis-systems to each other; we cannot avoid allowing the gauge factor to depend arbitrarily on position." 16 Here I am indebted to Johannes Huisman.

Where tetrads cannot remain constant, one has to suppose they vary. A flat real-valued phase connection A (see §4) alongside a curved A can of course be countenanced, but it is in the spirit of Weyl's argument for both to be flat or both curved. So if the tetrad varies, λ might as well too.

The group homomorphism h determines the Lie algebra homomorphism

h : w(2, C) → o(1, 3),
the Lie algebra w(2, C) being the direct sum sl(2, C) ⊕ iR1 2 , where iR = LieU(1). Doing away with the additive freedom λ (or rather iλ1 2 ) we're left with the isomorphism between w(2, C)/iR1 2 = sl(2, C) and o(1, 3). Instead of the phase e iλ ∈ U(1) we have iλ1 2 ∈ iR1 2 ; instead of U(1) we have the Lie algebra iR1 2 ; and instead of (4),

h(γ ⊕ iλ1 2 ) = h(γ) ∈ o(1, 3),
γ ∈ w(2, C). 17

Anholonomy

The additive freedom iλ1 2 is in the Lie algebra w(2, C) where the spin connection A has its values; and connections are there to generate parallel transport-in a direction. 18 A direction V ∈ T x M will therefore characterise the propagation of λ, whose infinitesimal variation δλ has to be linear in λ and in V . The object needed is a oneform; applied to the direction V it yields the infinitesimal generator A, V ∈ R, which then multiplies λ to produce the increment δλ = λ A, V . So there's a connection for tetrads, another for spinors, and a third one-A-for the residual U(1) freedom caught 'in between' tetrads and spinors.

The whole point of allowing the propagation of λ to depend on direction is to admit anholonomies. So the curvature

F = 1 2 F µν dx µ ∧ dx ν = dA = 1 2 (∂ µ A ν -∂ ν A µ )dx µ ∧ dx ν
17 Weyl (1929b, p. 348): "Dann ist aber auch die infinitesimale lineare Transformation dE der ψ, welche der infinitesimalen Drehung dγ entspricht, nicht vollständig festgelegt, sondern dE kann um ein beliebiges rein imaginäres Multiplum i • df der Einheitsmatrix vermehrt werden." Weyl (1929c, p. 291): "Then there remains in the infinitesimal linear transformation dE of ψ, which corresponds to the given infinitesimal rotation of the axis-system, an arbitrary additive term +idϕ • 1." 18 Weyl (1929b, p. 348): "Zur eindeutigen Festlegung des kovarianten Differentials δψ von ψ hat man also außer der Metrik in der Umgebung des Punktes P auch ein solches df für jedes von P ausgehende Linienelement -→ P P ′ = (dx) nötig. Damit δψ nach wie vor linear von dx abhängt, muß df = fp(dx) p eine Linearform in den Komponenten des Linienelements sein. Ersetzt man ψ durch e iλ , so muß man sogleich, wie aus der Formel für das kovariante Differential hervorgeht, df ersetzen durch dfdλ." Weyl (1929c, p. 291): "The complete determination of the covariant differential δψ of ψ requires that such a dϕ be given. But it must depend linearly on the displacement P P ′ : dϕ = ϕp(dx) p , if δψ shall depend linearly on the displacement. On altering ψ by multiplying it by the gauge factor e iλ we must at the same time replace dϕ by dϕdλ as is immediately seen from this formula of the covariant differential." Weyl's notation is confusing: whereas the one-form dλ (which is a differential) is necessarily exact, df and dϕ (my A) aren't.

of A will not necessarily vanish; and since F is exact, it is also closed:

dF = d 2 A = 1 6 (∂ µ F νσ + ∂ ν F σµ + ∂ σ F µν )dx µ ∧ dx ν ∧ dx σ = 0.
In F , A and dF = 0 Weyl saw19 the electromagnetic field, its potential and Maxwell's two homogeneous equations20 (which are the same-up to Hodge duality-as the other two, away from sources).

Final remark

Whatever its idiosyncrasies, Weyl's gauge argument at least avoids the exact connection A = dλ and vanishing curvature F = d 2 λ = 0 produced by the standard argument.

I thank Ermenegildo Caccese, Johannes Huisman, Thierry Levasseur and Jean-Philippe Nicolas for many valuable conversations and clarifications.

  Since, however, local gauge transformations can be shown as not observable, the received view proves itself untenable." It is untenable because the added term dλ is exact. But even if dλ is electromagnetically unobservable, it is quantum-mechanically observable: ϕ|P |ϕ = ϕ|P λ |ϕ .8[START_REF] Ryder | Quantum field theory[END_REF] p. 95: "the electromagnetic field arises naturally by demanding invariance of the action [ . . . ] under local (x-dependent) rotations[ . . . ]."

Yang & Mills (1954) p. 192: "It seems that this [(1) but with SU(2) instead of U(1)] is not consistent with the localized field concept that underlies the usual physical theories."

Weyl (1929b) p. 349, Weyl (1929c) pp. 291-2

∇ • B = 0 and ∇ × E + ∂tB = 0


Alexander Afriat Shortening

Alexander Afriat

Shortening the gauge argument

The gauge argument

One begins with a free field, of Dirac four-spinors ψ ∈ C 4 for instance. The Dirac Lagrangian L = ψ(i / ∂ -m)ψ is invariant under the global transformation

(1) ψ → e iκ ψ (whose existence is assumed for the time being), where "global" means that κ is the same everywhere. It is then argued 1 that L should also be invariant under the local transformation

(2)

ψ → ψ ζ = e iζ ψ,
where ζ : M → R is a smooth function on the base manifold M .

Most immediately what are we to make of the initial, central demand of local gauge invariance? The demand is anything but self-evident and presumably, in the context of the gauge argument, must be argued for on some 1 Göckeler & Schücker (1987) p. 48: "In physical terms we may interpret the requirement of local gauge invariance (independence of the fields at different spacetime points) as expressing the absence of (instantaneous) action at a distance." [START_REF] Ryder | Quantum field theory[END_REF] p. 93: "So when we perform a rotation in the internal space of ϕ at one point, through an angle Λ, we must perform the same rotation at all other points at the same time. If we take this physical interpretation seriously, we see that it is impossible to fulfil, since it contradicts the letter and spirit of relativity, according to which there must be a minimum time delay equal to the time of light travel. To get round this problem we simply abandon the requirement that Λ is a constant, and write it as an arbitrary function of space-time, Λ(x µ ). This is called a 'local' gauge transformation, since it clearly differs from point to point." Teller (2000) p. S469: "why should we expect invariance under a local phase transformation to begin with? The plausibility of such invariance probably arises with a misleading analogy with global phase transformations which can be imposed on individual state functions with no change of description." See also Sakurai (1967, p. 16), Aitchison & Hey (1982, p. 176), Mandl & Shaw (1984, p. 263), [START_REF] Ramond | Field theory: a modern primer[END_REF], pp. 183-91), O'Raifeartaigh (1997, p. 118). One is reminded of Weyl's rejection (1929a, p. 331;1929b, p. 286) of distant parallelism.

basis. Unlike the global invariance, the demand for the corresponding local invariance does not have an immediate physical counterpart. Is it to be taken as a direct implementation of some sort of unassailable first principle? If so, is the demand (or principle) something with which we are already familiar only in a different form?

A common justification for the demand of local gauge invariance in presenting the gauge argument is to present it as some sort of "locality" requirement. In outline, the "gauge locality argument" is that global gauge invariance is somehow at odds with the idea of a local field theory, and that to remedy this we must instead require local gauge invariance. This rather brief argument is just how Yang and Mills motivated the demand in their seminal 1954 paper, 2 very much setting the tone for subsequent treatments. Just what to make of this argument is not clear, however, there are many interrelated senses of locality that might be at issue. (Martin, 2002, p. S225) One gathers at any rate that considerable and varied efforts have been devoted to the transition from (1) to (2).

As things stand the Lagrangian is not invariant, because of the derivative in the first term of It is then argued that an interaction F = dA = d 2 ζ is thereby deduced, 4 whose potential A is dζ. But since d 2 vanishes the interaction does too, as has often been 2 Yang & Mills (1954) p. 192: "It seems that this [(1) but with SU(2) instead of U(1)] is not consistent with the localized field concept that underlies the usual physical theories."

L ζ = i ψζ / ∂ψ ζ -m ψψ. Writing ψζ / ∂ψ ζ = ψe -iζ γ µ ∂ µ e iζ ψ = ψγ µ (∂ µ + i∂ µ ζ)ψ we see that L ζ = ψ[iγ µ (∂ µ + i∂ µ ζ) -m]ψ has the derivative ∂ µ + i∂ µ ζ instead of ∂ µ .
3 My analysis owes much to [START_REF] Lyre | The principles of gauging[END_REF][START_REF] Lyre | Lokale Symmetrien und Wirklichkeit: eine Naturphilosophische Studie über Eichtheorien und Strukturenrealismus[END_REF]Lyre ( , 2004a,b),b). But

ϕ|P |ϕ = ϕU |U P U † |U ϕ = ϕU |P |U ϕ
seems relevant to his claim (2004b, pp. 649-51) that local phase transformations are not observable. I would say they are-unless one compensates to restore invariance. P. 651 he writes that: "local phase transformations are already unmasked as not observable. From this insight, however, the whole logic of the received view breaks down. Since the introduction of an interaction field as intended by the received view seemingly changes physics (those fields are even directly observable themselves), it is necesary from this view to consider local gauge transformations as changing physics as well in order to tell the story about compensation. The gauge argument is fertile enough to produce another two Lagrangians, 6

L A = j ∧ A = j µ A µ = ψγ µ A µ ψ and L F = F ∧ * F = - 1 4 F µν F µν ,
where the current density three-form

j = 1 3! ε µνστ j µ dx ν ∧ dx σ ∧ dx τ
corresponds to the vector with components j µ = ψγ µ ψ. One can either leave A = dζ in L ′ to offset (2), or balance

L ζ with L A in the sum L ′ = L ζ + L A .
Again, a Lagrangian L F derived from the gauge argument will vanish. But once the gauge argument has produced the exact potential A = dζ and vanishing interaction F = dA = d 2 ζ one can perhaps claim that A is no longer exact. The exact term dζ would then be subtracted from one that isn't 7 in the gauge transformation

(3)

A → A ′ = A -dζ.
The total Lagrangian L ′ + L F is indifferent to (2) and (3).

Global and local gauge transformations

Let us return to the global transformation (1), which adds the same angle κ everywhere on M . To do so one has to know where to start, there has to be an identity 1 = e i0 ∈ U(1) everywhere, a global identity I , of the gauge group G . The structure group G = U(1) is there to act on the typical fiber, which here is C 4 ; at a point x ∈ M , the identity 1 is the element that leaves any ψ x ∈ C 4 x unaltered; the global identity I ∈ G would leave a global section unaltered. But to leave a global section unaltered there has to be one in the first place. Since global sections do not exist in general, 8 the global gauge transformation (1) doesn't either, so the gauge argument can start with (2): "for the Lagrangian to remain invariant, the transformation (2) has to be balanced by the exact term dζ yielding the vanishing interaction d 2 ζ" and so on. The argument remains contrived and unconvincing, but at least the exertions needed to reach (2) from (1) are spared. The local transformation (2) may (or may not) require justification in 5 Auyang [START_REF] Aitchison | Gauge theories in particle physics[END_REF], p. 58), Brown (1999, pp. 50-3), Teller (2000, pp. S468-9), [START_REF] Lyre | The principles of gauging[END_REF][START_REF] Lyre | Lokale Symmetrien und Wirklichkeit: eine Naturphilosophische Studie über Eichtheorien und Strukturenrealismus[END_REF]Lyre ( , 2004a,b),b), Healey (2001, p. 438), Martin (2002, p. S229), [START_REF] Martin | On continuous symmetries and the foundations of modern physics[END_REF], p. 45), Catren (2008, pp. 512, 520). But the general structure of the covariant derivative is about right; [START_REF] Lyre | Lokale Symmetrien und Wirklichkeit: eine Naturphilosophische Studie über Eichtheorien und Strukturenrealismus[END_REF] p. 84: "Denn wenngleich das Eichprinzip [ . . . ] nicht zwingend auf nichtflache Konnektionen führt, so ist ja doch die in der kovarianten Ableitung vorgegebene Struktur des Wechselwirkungterms auch für den empirisch bedeutsamen Fall nichtverschwindender Feldstärken korrekt beschrieben. Diese Wechselwirkungsstruktur is also tatsächlich aus der lokalen Eichsymmetrie-Forderung hergeleitet."

6 Cf. Weyl (1929b, p. 283). 7 One can wonder what the gauge argument is for if the inexact potential A was already there to begin with. The exact term subtracted in (3) has more to do with the invariance of F = dA = dA ′ than with the gauge argument.

8 See Göckeler & Schücker (1987, §9.7) for instance. The matter is of course topological-a simplyconnected base manifold M admits global sections.

itself, regardless of context-but much less at any rate than if it is preceded by (1), which appears to represent a 'harmless' transformation from which effort is needed to reach and justify the 'troublesome' transformation (2). If (1) doesn't exist, (2) is neither troublesome nor harmless but all there is.

Of course (1) would-if available-be the natural place to start, as it corresponds to the only normal operator N such that L (ψ) = L (N ψ) without tinkering. The next most harmless normal operator is the unitary operator, whose action9 is given by (2); the progression from (1) to (2) would therefore be entirely natural. But now that we're no longer starting with (1), ( 2) is no longer the natural successor of an equally natural initial transformation, so why start with (2)? Because the only alternative is the transformation ψ → zψ (z ∈ C) corresponding to the most general normal operatorfrom which it is too hard to salvage the Lagrangian iz ψγ µ (z∂ µ + ∂ µ z)ψ + m|z| 2 ψψ.

  To offset (2) we therefore have to subtract the term i∂ µ ζ that alters L , yielding the covariant differential D = d -idζ with components D µ = ∂ µ -i∂ µ ζ. Writing / D = γ µ D µ , the balanced Lagrangian L ′ = ψζ (i / D -m)ψ ζ will be equal to L for all ζ. Another way of seeing that differentiation has to be balanced by dζ to offset (2): The momentum operator P becomes -id in the position representation; applied to ψ ζ it gives -idψ ζ = e iζ (-id + dζ)ψ ζ , in other words U P U † U ψ = P ζ ψ ζ , the position representation of the rotated momentum operator P ζ being -id + dζ. 3

  Since, however, local gauge transformations can be shown as not observable, the received view proves itself untenable." It is untenable because the added term dζ is exact. But even if dζ is electromagnetically unobservable, it is quantum-mechanically observable: ϕ|P |ϕ = ϕ|P ζ |ϕ .

	pointed out. 5
	4 Ryder (1996) p. 95: "the electromagnetic field arises naturally by demanding invariance of the action
	[ . . . ] under local (x-dependent) rotations [ . . . ]."
	2

In its 'diagonal' eigenrepresentation, in which the kernel becomes the multiplication operator e iζ , with just one variable.