S Pattofatto

H Tsitsiris

H Zhao

The instrumented dynamic perforation test applied to a composite shell

Perforation tests are commonly used on composites but give limited results. In this study, a single layer of a thermoplastic woven composite is tested at high velocity (45 m/s) by means of an instrumented perforation test. First, an inversed dynamic perforation tests is performed with a modified Hopkinson bar apparatus. This allows to measure accurately the perforation curve (force vs. displacement). Such a test is supplemented by the analysis of the strain displacement field measured by digital image correlation during the perforation process. This gives relevant information in case of inversed identification of several behavior parameters. This measurement technique allows to take into account the anisotropy of the material or an accurate estimation of the boundary conditions. A new experimental procedure is conducted for both quasi-static and dynamic tests. Results are presented concerning two points: the uncertainty of the measurements and the correction of boundary conditions from optical measurements.

INTRODUCTION

Due to their light weight, fibre reinforced composite materials are increasingly used in the automotive industry for environment purposes [1]. The use of composites for structural applications is also of great interest and this leads to the processing of new materials that need to be characterized [START_REF] Alcock | Low velocity impact performance of recyclable all-polypropylene composites[END_REF]. We focus on a long fibres composite, fully recyclable, with fast processability that is used in the car industry as the skin part of a sandwich structural material. It is made with long glass fibres and a polypropylene matrix. Such TP-composite is a good candidate for applications in automotive applications because of the common polypropylene matrix. Moreover, it is easy to form in order to design complex parts.

The reinforcement of the TP-composite is a fabric of long glass fibres yarns structured as a balanced weave of commercial Twintex ® . Twintex ® is a commingled E-glass and iPP filaments composite that is widely used in multilayers composite parts. The meso-structure of the studied material is therefore intrinsically anisotropic, that is the main property that we focus on. The viscoelasticity induced by the matrix and the damage induced by mechanical loading won't be studied here. The thickness of the shell is 0.8 mm. We also mention that a thin layer of PP is also present on one side of the TP-composite bound for linking the skin to the core material of the sandwich structure.

Classical experiments were performed to identify the macroscopic behavior of the shell material, based on tensile tests with three orientations: 0° and 90° (direction of fibers), and 45°, and the use of digital image correlation as an optical extensometer. It is clear that the description of the behavior with a basic linear orthotropic law is weak but this does not challenge the procedures presented here. The results are condensed as follows:

-(i) in the direction of the fibres, the material is elastic and brittle. Young's moduli can be accurately identified E 1 =10.3 GPa and E 2 =7.1 GPa (uncertainty <5 %), and Poisson's ratio are coarsely identified ! 12 =0.26 and ! 21 =0.18 (uncertainty <15 %), -(ii) in the 45° orientation, the response is non linear and exhibits hysteresis. In this case, the secant modulus is used to identify the shear modulus G12=292 MPa. In this way, the paper presented here is focused on one goal: the use of a so-called "perforation test" (that is, before fracture, precisely a flexural bending test) for the characterization of a TPcomposite shell. This goal is strongly dependent to the dynamic procedure because at high velocities (strain rate > 100 s -1 ) tensile tests are not common. On the other hand, perforation experiments conducted on drop weight devices are widely used on composites ( [START_REF] Belingardi | Influence of the laminate thickness in low velocity impact behavior of composite material plate[END_REF], and ASTM procedure [START_REF] Astm D | Standard test method for impact resistance of rigid plastic sheeting or parts by means of a tup (Falling Weight)[END_REF]). Such a test gives an overall result as a force vs. displacement curve that could be enriched. The aim of this work is therefore to provide new procedures for the instrumentation of perforation tests. Of course, this must require an inverse identification procedure [START_REF] Allix | Modified constitutive relation error identification strategy for transient dynamics with corrupted data: The elastic case[END_REF] because the complexity of the test cannot be described analytically. Thus, two experiments are used: the inversed perforation test based on the Hopkinson bar measurement technique, and the direct perforation test coupled with digital image correlation. We also mention that the bulge test is another analog experiment, widely used for the characterization of metal sheets, also for dynamic strain rates [START_REF] Grolleau | Biaxial Testing of Sheet Materials at High Strain Rates Using Viscoelastic Bars[END_REF]. The work presented here could be applied to such a test.

THE INVERSED PERFORATION TEST

The inversed perforation test is an original test based on the Hopkinson bar technique [START_REF] Zhao | Perforation of aluminium foam core sandwich panels under impact loading-An experimental study[END_REF][START_REF] Hockauf | Dynamic perforation and force measurement for lightweight materials by reverse ballistic impact[END_REF]. The socalled "perforation test" is considered: a disk of the TP-composite shell (" 48 mm) is held on its circonference and deformed statically or dynamically in its center by a rigid impactor of smaller diameter (" 16mm). The disk specimen is attached to a projectile and launched at around 45 m/s.The perforator is a long Hopkinson bar (marval steel, diam. 16 mm, length 6 m) initially at rest. Such an apparatus allows to measure the histories of perforation force F and displacement U during the whole perforation process with a good accuracy [START_REF] Zhao | Perforation of aluminium foam core sandwich panels under impact loading-An experimental study[END_REF]. The same experiments are performed for quasi-static loading as a reference (1 mm/s). Each test was repeated 3 times and tests were also done by reverting the specimen to analyze the effect of the PP layer (called face 2).

All the perforation curves are given in Figure 1. The results are the perforation force and displacement measured at the maximum of the curves, and the perforation energy calculated as the surface underneath the curve. All the results are gathered in table 1 It is shown that at 45 m/s there is a significant enhancement of the dynamic perforation force, a decrease of the perforation displacement, and an increase of the energy dissipated. Moreover, we can notice that the results depend strongly on which side of the shell is impacted and in particular the effect of the layer on the parameters is inversed between static and dynamic loadings. The analysis of post-mortem specimens shows a dramatic difference of the damaged area around the perforated zone, independently of the impacted face. In quasi-static, perforation occurs by macrocracking and the one or two cracks are located at the interface between yarns (Figure 1). In dynamic, the damaged zone is diffuse, all the yarns under the perforator are broken and videos of the perforation show the formation of a "debris cloud". This paper is not willing to explain neither the reason of this enhancement nor the effect of the PP layer.

As regards the perforation curves before fracture, quasi-static and dynamic curves are different: (i) static curve is non-linear due to the geometry of the experiment, and (ii) dynamic curve is roughly bi-linear, due to the interaction of the flexural wave created at the center with the fixing device.

static dynamic

Figur e 1. Perforation curves for dynamic (45 m/s) and static experiments. Comparison of fracture zone.

We limit here the analysis of the curves to those three values: force at the peak, displacement at the peak, and energy. In order to get closer to the deformation process during perforation a complementary method is proposed, presented in next section.

DIRECT PERFORATION AND DIGITAL IMAGE CORRELATION

A complementary experiment is performed. The goal of this experiment is to provide a measurement of the displacement field that can be used in an inverse identification procedure. A fast camera is used to record the deformation history of the face of the specimen during perforation. A perforator is fixed on a projectile launched at 45 m/s on a specimen held fixed on a framework. Thus, one face of the specimen can be observed by the camera, as depicted in Figure 2a (safe thanks to the use of a mirror placed at 45°). In this case, the perforation curve is no longer measured, that is why this test is said to be complementary to the test presented in previous section. Reference quasi-static perforation tests are done to compare with dynamic experiments. In this case measurement of force, displacement and recording of images can all be performed during the same test.

The parameters of the acquisition of images are the following: -for quasi-static tests: 1300x1950 at 1 fps (increment of perforation 1 mm), -for dynamic tests: 256x256 pixels at 30'000 fps (increment of perforation ca. 1.5 mm).

A digital image correlation (DIC) software developed in our laboratory [START_REF] Hild | Digital Image Correlation: From Displacement Measurement to Identification of Elastic Properties -A Review[END_REF], called Correli LMT , is used to calculate the displacement field of the specimen. This program is based on the comparison of two images (the deformed image g(x) and the image of reference f(x)); each image is discretized in linear quadrangles Q4 elements and the nodal displacement field is computed to minimize a quadratic error # defined as follows:

# 2 % u(x) & ' f (x) ( f (x) ) g(x) * + ,, 2 d x (1)
Without going in details into the technique, we mention that Correli LMT allows to compute displacement fields and subsequent strain fields, gives also a field of the residue of the minimization so that the quality of the computation is quantified, and the uncertainty on the displacement due to the algorithm can also be computed on the reference picture. As first insight of the computed results, two displacement fields in direction 1 of the picture are depicted in Figure 2b and2c, for quasi-static tests performed respectively on the TP-composite shell and for another reference test performed on a ductile A5 aluminium sheet considered as an isotropic material.

1 Figur e 2. Quasi-static test, (a) raw image of the specimen before the test, (b) 1_displacement field computed for a test on the shell TP-composite, (c) 1_displacement field computed for a test on aluminium sheet.

Preview of the displacement fields

Results of correlation presented in Figure 2 give a first insight of the improvement of the understanding of the perforation experiment thanks to imaging. The Figure 2c is taken as reference as it corresponds to a case of an isotropic behavior (A5 aluminium sheet, confirmed by a numerical simulation). Figure 2b shows that the anisotropy of the shell TP-composite is well depicted, showing roughly a separation of the isotropic "cockle" picture. This is also visible on the displacement result confirming that this is not due to sliding close to the fixing screws. The accuracy of the correlation procedure allows also to have local information that may be of interest. For example, the analysis of the strain map clearly shows the influence of the heterogeneity of the mesostructure of the material in the deformation process.

Figure 3 shows the evolution of the error field (equation 1) in the case of the dynamic experiment. The error is chosen because it is maximum where the variation of the images is more intense (due to deformation and also variation of light intensity) and therefore it shows clearly the position of the flexural wave propagating from the center to the boundary. The bilinear shape of the perforation curve is as expected due to the interaction of that wave with the boundary. Figur e 3. Visualisation of the propagation of the flexural wave during a dynamic perforation test (dt=35 -s)

Uncertainty analysis

The authors claim that the knowledge of the displacement field of the shell during a perforation process is a valuable measurement for an improved analysis of such a test. To confirm this point, an uncertainty analysis is conducted as regards two factors: (i) the quality of the images [START_REF] Hild | Digital Image Correlation: From Displacement Measurement to Identification of Elastic Properties -A Review[END_REF], (ii) the quality of the conservation of optical flow during the deformation process, depending on the stationarity of the lighting. The software Correli LMT allows to compute indicators a Regarding the conservation of optical flow, it is clear that it cannot be ensured when the shell is lighted by a directional light. This is the case in our tests and the effect of reflections and shades on the calculated displacement field is considered here. Figure 4 shows the value of error for different conditions of lighting. The results show the effect of lighting on the error, directly due to the way the error indicator is calculated (see equation 1). But it does not necessarily imply that the displacement on the efficiency of the computation of the displacement field. A given image is submitted numerically to a prescribed displacement u pre and the estimated displacement u est is returned. The results are that the raw quality of the images allows the measurement of the displacement with an accuracy of about 3/1000 pixels.

a The indicators are: the systematic error . u % u est ) u pre and the standard uncertainty / u % u est ) u est field is wrong. In Figure 4, the strain field is depicted and it is worth to notice the strain field is almost independent of the value of the error in that case. Therefore, when lighting is constant, the timeevolution of the error is a good indicator of the quality of the correlation. The value of the strain induced by this technical noise is about 0.5 %. This value is relatively high and is due (i) to the fact that the variation of lighting induces "shades" on the surface of the material that is not flat due to the weaves, and (ii) to the fact that the correlation was done with a small size of elements of 8 pixels. But in any case, this explains also the difficulty to obtain a good accuracy on the results.

Reference error map

$ $ $ $ max of error # max = 0.28 # max = 0.43 # max = 0.54

# max = 0.2 strain map $ $ $ $ strain 0 max !"#$% % 0 max !"#$& %$ 0 max !"#$% %$ 0 max !"#$& %$
Figur e 4. Error (field and maximum value) due to the variation of lighting

Correction of the boundary conditions

In case of the perforation experiments, the sliding of the specimen at the boundary is one of the critical questions because it is very sensitive and usually it is not measured. The great advantage of the imaging is that displacement at the boundary can be extracted from the displacement field computed by DIC. First we can suppose that close to the framework on which the specimen is fixed, the out-ofplane displacements are negligible. Two results are presented in figure 5. They show the evolution of the displacements U and V along a circle the diameter of which is 90 % of the diameter of the ring on which the specimen is fixed. These displacements here take into account both the out-of-plane displacements, the in-plane due to deformation and the sliding at the boundary. These displacements can then be used as a boundary condition in a FE calculation of the experiment. The results show that without any filtering, the noise on the boundary condition is less than 0.01 mm.

CONCLUSIONS AND PROSPECTS

Two original experiments were presented, dealing with the dynamic characterization of a TPcomposite shell at high impact velocities (45 m/s). The first experiment is a modified Hopkinson bar test applied to perforation. Contrary to a classical drop-weight test, the use of a gas-gun allows to reach high impact velocities and the Hopkinson bar ensures an accurate measurement of force and displacement. The drawback of the test is that the geometry of the specimen is contained by the inner diameter of the barrel of the gas gun. Results are presented. The second experiment is a direct perforation test coupled with a digital image correlation technique. The uncertainty of the measurement is discussed, and in particular the effect of the lighting. The computed displacement fields are analyzed for quasi-static and dynamic experiments. The results show that displacements can be computed with an uncertainty of about 0.1 mm in best conditions. In case of dynamic test, the low resolution implies that the element size is chosen at 8 pixels and the direct consequence is a wellknown decrease of the accuracy. For quasi-static case, the displacement field is accurate and a result of extraction along a circle is presented as for the use as boundary condition in a FE computation.

As prospects, we put the stress on the fact that in this paper, out-of-plane displacements (OoPD) are not corrected and influence the measurement of the displacement by digital image correlation. This can be solved and two strategies are for example proposed: either the OoPD are corrected numerically during the inversed identification procedure (this requires an easy calibration during the test), or they can be taken into account directly in the measurement using for example a technique of stereo-correlation. This is the main prospect of this work because such a technique is now available in our lab.

Figur e 5 .

 5 Figur e 5. Result of extraction of the displacement along a circle close to the boundary.

Table 1 .

 1 . Results of perforation experiments.

		Perforation force	Perforation displ.	Perforation energy
		mean [range] (N)	mean [range] (mm)	mean [range] (J )
		Dyn.	St.	Rel.	Dyn.	St.	Rel.	Dyn.	St.	D/S
	Face 1	2300	1900	+20%	8 [1]	12 [2] -33% 12.1	10.4	+16%
		[600]	[200]					[1.3]	[1.6]
	Face 2	2700	1350	+99%	9 [0]	10 [2] -10% 13.6	7.1	+92%
		[100]	[300]					[3.2]	[0.9]
	F2/F1	+17%	-24%		13%	-16%		+12%	-32%

1/ 2 .


Sylvain Schmitz
email: sylvain.schmitz@lsv.ens-cachan.fr

An Experimental Ambiguity Detection Tool *

Keywords: grammar verification, disambiguation, GLR

Although programs convey an unambiguous meaning, the grammars used in practice to describe their syntax are often ambiguous, and completed with disambiguation rules. Whether these rules achieve to the removal of all the ambiguities while preserving the original intended language can be difficult to ensure. We present an experimental ambiguity detection tool for GNU Bison, and illustrate how it can assist a grammatical development for a subset of Standard ML.

Introduction

With the broad availability of parser generators that implement Generalized LR (GLR) [START_REF] Tomita | Efficient Parsing for Natural Language[END_REF] or the [START_REF] Earley | An efficient context-free parsing algorithm[END_REF] algorithm, it might seem that struggles with the dreaded report grammar.y: conflicts: 223 shift/reduce, 35 reduce/reduce are now over. General parsers of these families simulate the various nondeterministic choices in parallel with good performance, and return all the legitimate parses for the input (see [START_REF] Scott | Right nulled GLR parsers[END_REF] for a survey).

What our naive account overlooks is that all the legitimate parses according to the grammar might not always be correct in the intended language. With programming languages in particular, a program is expected to have a unique interpretation, and thus a single parse should be returned. Nevertheless, the grammar developed to describe the language is often ambiguous: ambiguous grammars are more concise and readable [START_REF] Aho | Deterministic parsing of ambiguous grammars[END_REF]. The language definition should therefore include some disambiguation rules to decide which parse to choose.

In this paper, we present a tool for GNU Bison [START_REF] Donnely | Bison version 2.3[END_REF] 1 that pinpoints possible ambiguities in context-free grammars (CFGs). Grammar and parser developers can then use the ambiguities reported by the

⟨dec⟩ - → fun ⟨fvalbind ⟩ ⟨fvalbind ⟩ - → ⟨fvalbind ⟩ ′ | ′ ⟨sfvalbind ⟩ | ⟨sfvalbind ⟩ ⟨sfvalbind ⟩ - → vid ⟨atpats⟩ = ⟨exp⟩ ⟨atpats⟩ - → ⟨atpats⟩ ⟨atpat⟩ | ⟨atpat⟩ ⟨exp⟩ - → case ⟨exp⟩ of ⟨match⟩ | vid ⟨match⟩ - → ⟨match⟩ ′ | ′ ⟨mrule⟩ | ⟨mrule⟩ ⟨mrule⟩ - → ⟨pat⟩ => ⟨exp⟩ ⟨pat⟩ - → vid ⟨atpat⟩ ⟨atpat⟩ - → vid
Figure 1: Syntax of function value binding and case expressions in Standard ML. We translated the rules from their original extended form into BNF. We write ⟨nonterminals⟩ between angle brackets and terminals as such, except for the terminal alternation symbol ′ | ′ , quoted in order to avoid confusion with the choice meta character |. The Standard ML compilers consistently reject this correct input, often pinpointing the error at the equal sign in "| filterP ([], l ) = rev l". Let us investigate why they behave this way.

The Conflict

We implemented our set of grammar rules in GNU Bison [START_REF] Donnely | Bison version 2.3[END_REF], and the result of a run in LALR(1) mode is a single shift/reduce conflict, a nondeterministic choice between two parsing actions: The conflict has to be solved in two different places with the program of If we choose arbitrarily one of the actions-shift or reduce-over the other, we obtain the parses drawn in Figure 2. The shift action is chosen by default by Bison, and ends on a parse error when seeing the equal sign where a double arrow was expected, exactly where the Standard ML compilers report an error (Figure 2d).

We could make the correct decision if we had more information at our disposal. The "=" sign in the lookahead string "| filterP ([], l ) = rev l" indicates that the alternative is at the topmost function value binding ⟨fvalbind ⟩ level, and not at the "case" level, or it would be a "=>" sign. But the sign can be arbitrarily far away in the lookahead string: an atomic pattern ⟨atpat⟩ can derive a sequence of tokens of unbounded length. The conflict requires an unbounded lookahead.

Example 2 The issue is made further complicated by the presence of a dangling ambiguity:

case a of b => case b of c => c | d => d
In this expression, should the dangling "d => d" matching rule be attached to "case b" or to "case a"? The Standard ML definition indicates that the matching rule should be attached to "case b". In this case, the shift should be chosen rather than the reduction, which explains the choice made by developers of the various Standard ML parsers. This issue in the syntax of Standard ML is one of its few major defects according to a survey by [START_REF] Rossberg | Defects in the revised definition of Standard ML[END_REF]:

[Parsing] this would either require horrendous grammar transformations, backtracking, or some nasty and expensive lexer hack.

Fortunately, the detailed analysis of the conflict we conducted, as well as the ugly or expensive solutions mentioned by Rossberg, are not necessary with a general parser.2

General Parsing

A general parser returns all the possible parses for the provided input, and as such discards the incorrect parses of Figures 2a and2d and only returns the correct ones of Figures 2b and2c. In particular, a generalized LALR(1) parser explores the two possibilities of the conflict, until it reaches the "=>" or "=" sign, at which point the incorrect partial parses of Figures 2a and2d fail.

Our tool tackles an issue that appeared with the recent popularity of general algorithms for programming languages parsers. The user does not know a priori whether the conflict reported by Bison in the LALR(1) automaton is caused by an ambiguity or by an insufficient lookahead length. A casual investigation of its source might only reveal the unbounded lookahead aspect of the conflict as with Example 1, and overlook the ambiguity triggered by embedded case expressions like the one of Example 2. The result might be a collection of parse trees-a parse forest-where a single parse tree was expected, hampering the reliability of the computations that follow the parsing phase.

Two notions pertain to the current use of parse forests in parsing tools.

• The sharing of common subtrees bounds the forest space complexity by a polynomial function of the input length [START_REF] Billot | The structure of shared forests in ambiguous parsing[END_REF]. Figure 3 shows a shared forest for our ambiguity, with a topmost ⟨match⟩ node that merges the two alternative interpretations of the input of Example 2.

• [START_REF] Klint | Using filters for the disambiguation of context-free grammars[END_REF] developed the general notion of disambiguation filters that reject some of the trees of the parse forest, with the hope of ending the selection process with a single tree. Such a mechanism is implemented in one form or in another in many GLR tools, including SDF (van den Brand et al., 2002), Elkhound (McPeak and[START_REF] Mcpeak | Elkhound: A fast, practical GLR parser generator[END_REF], and Bison [START_REF] Donnely | Bison version 2.3[END_REF].

Merge Functions

Unexpected ambiguities are acute with GLR parsers that compute semantic attributes as they reduce partial trees. The GLR implementations of GNU Bison [START_REF] Donnely | Bison version 2.3[END_REF][START_REF] Donnely | Bison version 2.3[END_REF]of Elkhound (McPeak and[START_REF] Mcpeak | Elkhound: A fast, practical GLR parser generator[END_REF] are in this situation. Attribute values are synthesized for each parse tree node, and in a situation like the one depicted in Figure 3, the values obtained for the two alternatives of a shared node have to be merged into a single value for the shared node as a whole. The user of these tools should thus provide a merge function that returns the value of the shared node from the attributes of its competing alternatives.

Failure to provide a merge function where it is needed forces the parser to choose arbitrarily between the possibilities, which is highly unsafe. Another line of action is to abort parsing with a message exhibiting the ambiguity; this can be set with an option in Elkhound, and it is the behavior of Bison.

A Detailed Knowledge of Ambiguities

Example 3 Let us suppose that the user has encountered the ambiguity of Example 2, and is using a disambiguation filter (in the form of a merge function in Bison or Elkhound) that discards the dotted alternative of Figure 3, leaving only the correct parse according to the Standard ML definition. A simple way to achieve this is to check whether we are reducing using rule ⟨match⟩ -→ ⟨match⟩ ′ | ′ ⟨mrule⟩ or with rule ⟨match⟩ -→ ⟨mrule⟩. Filters of this variety are quite common, and are given a specific dprec directive in Bison, also corresponding to the prefer and avoid filters in SDF2 [START_REF] Van Den Brand | Disambiguation filters for scannerless generalized LR parsers[END_REF]. The above solution is unfortunately unable to deal with yet another form of ambiguity with ⟨match⟩, namely the ambiguity encountered with the input:

case a of b => b | c => case c of d => d | e => e
Indeed, with this input, the two shared ⟨match⟩ nodes are obtained through reductions using the same rule ⟨match⟩ -→ ⟨match⟩ ′ | ′ ⟨mrule⟩, as can be seen in Figure 4. Had we trusted our filter to handle all the ambiguities, we would be running our parser under a sword of Damocles.

This last example shows that a precise knowledge of the ambiguous cases is needed for the development of a reliable GLR parser. While the problem of detecting ambiguities is undecidable, conservative answers could point developers in the right direction.

Detecting Ambiguities

Our tool is implemented in C as a new option in GNU Bison that triggers an ambiguity detection computation instead of the parser generation. The output of this verification on our subset of the Standard ML grammar reports two pairs of positions in the grammar that exhibit potential ambiguities:

2 potential ambiguities with LR(0) precision detected: (match -> mrule . , match -> match . '|' mrule ) (match -> match . '|' mrule , match -> match '|' mrule . )
From this ambiguity report, two things can be noted: that user-friendliness is not a strong point of the tool in its current form, and that the two detected ambiguities correspond to the two ambiguities of Examples 2 and 3. Furthermore, the reported ambiguities do not mention anything visibly related to the difficult conflict of Example 1.

Overview

Our ambiguity checking algorithm attempts to find ambiguities as two different parse trees describing the same sentence. Of course, there is in general an infinite number of parse trees with an infinite number of derived sentences, and we make therefore some approximations when visiting the trees.

We consider here approximations based on LR(0) items: a dot in a grammar production -→ ⋅ can also be seen as a position in an elementary tree-a tree of height one-with root and leaves labeled by . When moving from item to item, we are also moving inside all the syntax trees that contain the corresponding elementary trees. The LR(0) item approximation is such that positions represented by the same item are considered as identical regardless of their actual context; Figure 5 presents two such equivalent positions in a derivation tree. We call this equivalence relation item 0 .

In order to find potential ambiguities modulo our approximation, we further need to walk through the derivation trees. With LR(0) items, this means that we can move inside a dotted production without any loss of precision, but that upwards moves are performed regardless of any context. These eligible single moves from item to item are in fact the transitions in a nondeterministic LR(0) automaton (thereafter called LR(0) NFA). All the moves from item to item that we describe in the following can be checked on the trees of Figures 2 and3.

Since we want to find two different trees, we work with pairs of concurrent items, starting from a pair ( -→ ⋅ ⟨dec⟩ $, - → ⋅ ⟨dec⟩ $) at the beginning of all trees, and ending on a pair ( -

→ ⟨dec⟩ $ ⋅ , - → ⟨dec⟩ $ ⋅ ).
Between these, we pair items that could be reached upon reading a common prefix of a sentential form, hence following trees that derive the same sentence modulo our approximations.

The notion of equivalence of positions in derivation trees is the basis for a framework for context-free grammar approximations, which generalizes more complex constructions, like the item Π equivalence of LR-Regular parsers [START_REF] Čulik | LR-Regular grammars-an extension of LR( ) grammars[END_REF][START_REF] Heilbrunner | Tests for the LR-, LL-, and LC-Regular conditions[END_REF]. The LR(0) NFA is a special case of a more general position automaton that abstracts left-to-right walks inside the grammar trees. Our algorithm in its full generality guarantees that all ambiguities are caught for any such position automaton [START_REF] Schmitz | Conservative ambiguity detection in context-free grammars[END_REF].

Example Run

We present here our algorithm with LR(0) items on the relevant portion of our grammar. Let us start with the pair of items reported as being in conflict by Bison; just like Bison, our algorithm has found out that the two positions might be reached by reading a common prefix from the beginning of the input:

(⟨match⟩ - → ⟨match⟩ ⋅ ′ | ′ ⟨mrule⟩, ⟨exp⟩ - → case ⟨exp⟩ of ⟨match⟩ ⋅ ) (A)
Unlike Bison, when confronted with a conflict, the algorithm attempts to see whether we can keep reading the same sentence until we reach the end of the input. Since we are at the extreme right of the elementary tree for rule ⟨exp⟩ -→ case ⟨exp⟩ of ⟨match⟩, we are also to the immediate right of the nonterminal ⟨exp⟩ in some rule right part. Our algorithm explores all the possibilities, thus yielding the three pairs:

(⟨match⟩ - → ⟨match⟩ ⋅ ′ | ′ ⟨mrule⟩, ⟨mrule⟩ - → ⟨pat⟩=>⟨exp⟩ ⋅ ) (A.1) (⟨match⟩ - → ⟨match⟩ ⋅ ′ | ′ ⟨mrule⟩, ⟨exp⟩ - → case ⟨exp⟩ ⋅ of ⟨match⟩) (A.2) (⟨match⟩ - → ⟨match⟩ ⋅ ′ | ′ ⟨mrule⟩, ⟨sfvalbind ⟩ - → vid ⟨atpats⟩ = ⟨exp⟩ ⋅ ) (A.3)
Applying the same idea to the conflicting pair (A.1), we should explore all the items with the dot to the right of ⟨mrule⟩.

(⟨match⟩ - → ⟨match⟩ ⋅ ′ | ′ ⟨mrule⟩, ⟨match⟩ - → ⟨mrule⟩ ⋅ ) (A.1.1) (⟨match⟩ - → ⟨match⟩ ⋅ ′ | ′ ⟨mrule⟩, ⟨match⟩ - → ⟨match⟩ ′ | ′ ⟨mrule⟩ ⋅ ) (A.1.
2) At this point, we find [⟨match⟩ -→ ⟨match⟩ ⋅ ′ | ′ ⟨mrule⟩], our competing item, among the items with the dot to the right of ⟨match⟩: from our approximations, the strings we can expect to the right of the items in the pairs (A.1.1) and (A.1.2) are the same, and we report the pairs as potential ambiguities.

Our ambiguity detection is not over yet: from (A.3), we can also reach (showing only the relevant possibilities):

(⟨match⟩ - → ⟨match⟩ ⋅ ′ | ′ ⟨mrule⟩, ⟨fvalbind ⟩ - → ⟨sfvalbind ⟩ ⋅ ) (A.3.1) (⟨match⟩ - → ⟨match⟩ ⋅ ′ | ′ ⟨mrule⟩, ⟨fvalbind ⟩ - → ⟨fvalbind ⟩ ⋅ ′ | ′ ⟨sfvalbind ⟩) (A.3.1.1)
In this last pair, the dot is to the left of the same symbol, meaning that the following item pair might also be reached by reading the same string from the beginning of the input:

(⟨match⟩ - → ⟨match⟩ ′ | ′ ⋅ ⟨mrule⟩, ⟨fvalbind ⟩ - → ⟨fvalbind ⟩ ′ | ′ ⋅ ⟨sfvalbind ⟩) (B)
Because the dot is to the immediate left of a nonterminal symbol, it is also at the beginning of all the right parts of the productions of this symbol, yielding successively:

(⟨mrule⟩ - → ⋅ ⟨pat⟩=>⟨exp⟩, ⟨fvalbind ⟩ - → ⟨fvalbind ⟩ ′ | ′ ⋅ ⟨sfvalbind ⟩) (B.1) (⟨mrule⟩ - → ⋅ ⟨pat⟩=>⟨exp⟩, ⟨sfvalbind ⟩ - → ⋅ vid ⟨atpats⟩ = ⟨exp⟩) (B.1.1) (⟨pat⟩ - → ⋅ vid ⟨atpat⟩, ⟨sfvalbind ⟩ - → ⋅ vid ⟨atpats⟩ = ⟨exp⟩) (B.1.1.1) (⟨pat⟩ - → vid ⋅ ⟨atpat⟩, ⟨sfvalbind ⟩ - → vid ⋅ ⟨atpats⟩ = ⟨exp⟩) (C) (⟨pat⟩ - → vid ⋅ ⟨atpat⟩, ⟨atpats⟩ - → ⋅ ⟨atpat⟩) (C.1) (⟨pat⟩ - → vid ⟨atpat⟩ ⋅ , ⟨atpats⟩ - → ⟨atpat⟩ ⋅ ) (D) (⟨mrule⟩ - → ⟨pat⟩ ⋅ =>⟨exp⟩, ⟨atpats⟩ - → ⟨atpat⟩ ⋅ ) (D.1) (⟨mrule⟩ - → ⟨pat⟩ ⋅ =>⟨exp⟩, ⟨sfvalbind ⟩ - → vid ⟨atpats⟩ ⋅ = ⟨exp⟩) (D.1.1)
Our exploration stops with this last item pair: its concurrent items expect different terminal symbols, and thus cannot reach the end of the input upon reading the same string. The algorithm has successfully found how to discriminate between the two possibilities in conflict in Example 1.

Presentation of the Algorithm

The example run presented above relates pairs of items. We call this relation the mutual accessibility relation ma, and define it as the union of several primitive relations:

mas for terminal and nonterminal shifts, holding for instance between pairs (A.3.1.1) and (B), but also between (C.1) and (D), mae for downwards closures, holding for instance between pairs (B) and (B.1), mac for upwards closures in case of a conflict, i.e. when one of the items in the pair has its dot to the extreme right of the rule right part and the concurrent item is different from it, holding for instance between pairs (A.1) and (A.1.1). Formally, our notion of a conflict coincides with that of Aho and Ullman (1972, Theorem 5.9).

The algorithm thus constructs the image of the initial pair ( ′ -→ ⋅ $, ′ - → ⋅ $) by the reflexive transitive closure ma * of the ma relation. If at some point we reach a pair holding two copies of the same item from a pair with different items, we report an ambiguity. 3 The algorithm is reminiscent of noncanonical parsing techniques [START_REF] Szymanski | Noncanonical extensions of bottomup parsing techniques[END_REF], and we call it the noncanonical unambiguity (NU) test.

The size of the ma relation is bounded by the square of the size of the position automaton, here the LR( 0

Implementation Details

The experimental tool currently implements the algorithm with LR(0) items, SLR(1) items-meaning that simple lookahead sets are considered for the conflict relation mac-and LR(1) items. Although the space required by LR(1) item pairs is really large, we need this level of precision in order to guarantee an improvement over the LALR(1) construction. The implementation is changed in a few details.

NFA Size Optimization

We construct a nondeterministic automaton [START_REF] Hunt | Operations on sparse relations and efficient algorithms for grammar problems[END_REF][START_REF] Grune | Parsing Techniques: A Practical Guide[END_REF] whose states are either dotted rule items of form -→ ⋅ , or some nonterminal items of form ⋅ or ⋅ . For instance, a nonterminal item would be used when computing the mutual accessibility of (A.1) and before reaching (A.1.1):

(⟨match⟩ - → ⟨match⟩ ⋅ ′ | ′ ⟨mrule⟩, ⟨mrule⟩ ⋅ ).
The size of the NFA then becomes bounded by (| |) in the LR(0) and SLR(1) case, and (| || | 2 )-where | | is the number of terminal symbols-in the LR(1) case, and the complexity of the algorithm is thus bounded by the square of these numbers.

Static Disambiguation

We consider the associativity and static precedence directives [START_REF] Aho | Deterministic parsing of ambiguous grammars[END_REF] of Bison in the conflict relation mac, and thus we do not report statically resolved ambiguities. Dynamic merge functions are a different matter, discussed in Section 5.3.

Ordering Conflicts

We order our items pairs to avoid redundancy in reduce/reduce conflicts. In such a conflict, we can choose to follow one reduction or the other, and we might find a point of ambiguity sooner or later depending on this choice. Let us consider for instance the grammar with rules

- → , - → | , - → .
The conflicting positions

( - → ⋅ , - → ⋅ ) (E) can reach through mac * ( - → ⋅ , - → ⋅ ) (E.1) ( - → ⋅ , - → ⋅ ) (E.2) ( - → ⋅ , - → ⋅ ) (E.2.1) ( - → ⋅ , - → ⋅ ) (E.2.1.1)
where the pairs (E.1) and (E.2.1.1) denote the same potential ambiguity.

The same kind of issue was met by McPeak and Necula with Elkhound (Mc-Peak and Necula, 2004), where a strict bottom-up order was enforced using an ordering on the nonterminals and the portion of the input string covered by each reduction.

We solve our issue in a similar fashion, the difference being that we do not have a finite input string at our disposal, and thus we adopt a more conservative ordering. We say that and are in a right corner relation, noted ∠ , if there is a rule -→ . Our order is then the transitive reflexive closure ∠ * of the right corner relation. In a reduce/reduce conflict between reductions to and , we follow the reduction of if ∕ ∠ * or if both ∠ * and ∠ * . In our small example, this disallows the exploration of the pair (E.2) and thus of the remaining pairs (E.2.1) and (E.2.1.1).

Experimental Comparisons

The choice of a conservative ambiguity detection algorithm is currently rather limited. Nevertheless, several parsing techniques define proper subsets of the unambiguous grammars, and as such can be employed as unambiguity tests. The most common of all is the LALR(1) construction, but, as argued earlier, the presence of a conflict is not very informative as far as ambiguity is concerned. We present in this section several comparisons between our algorithm and its competitors.

Other Conservative Algorithms

LR( ) Construction

The class of LR( ) grammars uses a fixed amount of lookahead to dispel conflicts. Although it is widely considered that even a setting of = 1 leads to impractical parser sizes, there exist compression techniques, and a few implementations are available (e.g. MSTA [START_REF] Makarov | MSTA (syntax description translator[END_REF]).

The grammar family 3 demonstrates the complexity gains with our algorithm as compared to LR( ) parsing:

- → | , - → | , 1 - → , 2 - → 1 1 , . . . , - → -1 -1
( 3 ) While a LR(2 ) test is needed in order to tell that 3 is unambiguous, the grammar is found unambiguous with our algorithm using LR(0) items.

Following the results on LR( ) testing [START_REF] Hunt | Operations on sparse relations and efficient algorithms for grammar problems[END_REF], we implemented a canonical LR test in our tool using the same item pairing technique as for the NU test. More precisely, we compute the image of the initial pair of items through (mas ∪ mae) * and report a LR conflict as soon as we find an item pair that could follow a conflict relation mac.

LR-Regular Construction

Beyond LR( ) parsing, LR-Regular parsing [START_REF] Čulik | LR-Regular grammars-an extension of LR( ) grammars[END_REF]) employs a regular approximation of the right context of conflicts in an attempt to find the correct parsing action. In practice it explores a regular cover of the right context of LR conflicts with a finite automaton [START_REF] Baker | Extending lookahead for LR parsers[END_REF][START_REF] Boullier | Contribution à la construction automatique d'analyseurs lexicographiques et syntaxiques[END_REF].

Grammar 5 is a non-LRR grammar with rules

- → | , - → , - → , - → | .
( 5 )

It is found to be unambiguous by our algorithm using LR(0) items. Still with our item pairing approach, we implemented a LRR test [START_REF] Heilbrunner | Tests for the LR-, LL-, and LC-Regular conditions[END_REF], where item pairs after a conflict-i.e. after a mac relation-have to follow the same terminal symbols (and not any symbol in as with mas), and can move downwards and upwards freely. A potential ambiguity is reported whenever a pair containing twice the same item is reached at some point during the exploration of the right context of conflicts, as with the NU test.

Horizontal and Vertical Ambiguity

A different approach, unrelated to any parsing method, was proposed by [START_REF] Brabrand | Analyzing ambiguity of context-free grammars[END_REF] with their horizontal and vertical unambiguity test (HVRU). Horizontal ambiguity appears with overlapping concatenated languages, and vertical ambiguity with non-disjoint unions; their method thus follows exactly how the context-free grammar was formed. Their intended application is to test grammars that describe RNA secondary structures [START_REF] Reeder | Effective ambiguity checking in biosequence analysis[END_REF].

Grammars 6 and 7 show that our method is not comparable with the horizontal and vertical ambiguity detection method of Brabrand et al.. Grammar 6 is a palindrome grammar with rules 1 compiles the results obtained on these grammars. The "LALR(1)" column provides the total number of conflicts (shift/reduce as well as reduce/reduce) reported by Bison, the "HVRU" column the number of potential ambiguities (horizontal or vertical) reported by the HVRU algorithm with unfolding, and the "NU(item 0 )" column the number of potential ambiguities reported by our algorithm with LR(0) items. For completeness, we also present the results of our tool on the RNA grammars of [START_REF] Reeder | Effective ambiguity checking in biosequence analysis[END_REF] in Table 2.

- → | | | | ( 6 )

Precision Settings

Several conservative ambiguity detection methods are thus possible: LR( ) and LR-Regular testing, horizontal and vertical unambiguity testing, and NU testing. Each of these methods can employ different scales of precision:

• our implementation of the LR, LR-Regular and NU methods can employ LR(0), SLR(1) or LR(1) items and notions of conflicts;

• GNU Bison and MSTA further provide respectively a LALR(1) precision and a LR( ) precision with an arbitrary fixed for the LR method;

• the results published by Brabrand et al. with horizontal and vertical unambiguity also take advantage of the possibility to unfold the grammar in order to improve the precision of their tests. The approximation they build without unfolding follows the technique of [START_REF] Mohri | Regular approximations of context-free grammars through transformation[END_REF], and is slightly better than the one provided by LR(0) items, because they identify the strongly regular portions of the grammar and avoid some unnecessary approximations. The results we present in the following for HVRU ambiguity detection do not take unfolding into account, but we dedicate a few more words on the matter in the addendum at the end this section.

Experiments on Grammars for Programming Languages

We ran our implementations of the LR, LRR and NU methods on seven different ambiguous grammars for programming languages:

Pascal an ISO-7185 Pascal grammar retrieved from the comp.compilers FTP at ftp://ftp.iecc.com/pub/file/, it is LALR(1) except for a dangling else ambiguity, Mini C a simplified C grammar written by Jacques Farré for a compilers course, it is LALR(1) except for a dangling else ambiguity, ANSI C (Kernighan and Ritchie, 1988, Appendix A.13), also retrieved from the comp.compilers FTP. The grammar is LALR(1), except for a dangling else ambiguity. The ANSI C' grammar is the same grammar modified by setting typedef names to be a nonterminal, with a single production ⟨typedef -name⟩ -→ identifier . The modification reflects the fact that GLR parsers should not rely on side-effects like the lexer feedback hack for disambiguation (see McPeak and Necula, 2004, Section 5.1).

Standard ML, extracted from the language definition (Milner et al., 1997, Appendix B). As mentioned in Section 2, this is a highly ambiguous grammar, and no effort whatsoever was made to ease its implementation with a parser generator.

Elsa C++, developed with the Elkhound GLR parser generator [START_REF] Mcpeak | Elkhound: A fast, practical GLR parser generator[END_REF], and a smaller version without class declarations nor function bodies. Although this is a grammar written for a GLR parser generator, it allows deterministic parsing whenever possible in an attempt to improve performance.

In order to provide a better ground for comparisons between LR, LRR and NU testing, we implemented an option that computes the number of initial LR(0) item pairs in conflict-for instance pair (A)-that can reach a point of ambiguity-for instance pair (A.1.1)-through the ma relation. Table 3 presents the number of such initial conflicting pairs with our tests when employing LR(0) items, SLR(1) items, and LR(1) items. We completed our implementation by counting conflicting LR(0) item pairs for the LALR(1) conflicts in the parsing tables generated by Bison, which are shown in the LALR(1) column of Table 3.

This measure of the initial LR(0) conflicts is far from perfect. In particular, our Standard ML subset has a single LR(0) conflict that mingles an actual ambiguity with a conflict requiring an unbounded lookahead exploration: the measure would thus show no improvement when using our test. The measure is not comparable with the numbers of potential ambiguities reported by NU; for instance, NU(item 1 ) would report 89 potential ambiguities for Standard ML, and 52 for ANSI C'. Another means to compare ambiguity detection tools is thus investigated in the next subsection.

Although we ran our tests on a machine equipped with a 3.2GHz Xeon and 3GiB of physical memory, several tests employing LR(1) items exhausted the memory, resulting in the "-" entries in Table 3. The explosive number of LR(1) items is also responsible for a huge slowdown: for the small Elsa grammar, the NU test with SLR(1) items ran in 0.22 seconds, against more than 2 minutes for the corresponding canonical LR(1) test (and managed to return a better conflict report).

Micro-Benchmarks

Basten (2008) compared several means to detect ambiguities in context-free grammars, including our own implementation in GNU Bison, the AMBER generative test [START_REF] Schröer | AMBER, an ambiguity checker for context-free grammars[END_REF], and the MSTA LR( ) parser generator [START_REF] Makarov | MSTA (syntax description translator[END_REF]. Also confronted with the difficulty of measuring ambiguity in a meaningful way, he opted for a micro-benchmark approach, performing the tests on 36 small unambiguous grammars and 48 ambiguous ones from various sources.

Basten's Results

The conservative accuracy ratios [START_REF] Basten | The usability of ambiguity detection methods for contextfree grammars[END_REF] obtained with our tool, computed as the number of grammars correctly classified as unambiguous, divided by the number of tested unambiguous grammars, were of 61%, 69%, and 86% in the LR(0), SLR(1), and LR(1) modes respectively. This compares rather well to the LR( ) tests, where the ratio drops to 75%, with attempted values as high as 50. Interestingly, when run against the same collection, our LRR test with LR(1) precision chokes on the same grammars as the LR( ) tests, and obtains the same 75% ratio. Furthermore, the grammars on which the NU(item 1 ) test failed were all of the same mold (1-, 2-, and 4-letters palindromes, and the RNA grammars RNA 3 and RNA 7 of [START_REF] Reeder | Effective ambiguity checking in biosequence analysis[END_REF]).

A Larger Collection

We gathered a few more unambiguous grammars from programming languages constructs in order to improve the representativity of Basten's grammar collection in this domain.

The comp.compilers Collection A first set of seven unambiguous grammars was found in the comp.compilers archive when querying the word "conflict" and after ruling out ambiguous grammars and LL-related conflicts:4 90-10-042 an excerpt of the YACC syntax, which has an optional semicolon as end of rule marker that makes it LR(2); The Literature Collection A second set of nine unambiguous grammars was compiled using grammars from the literature, notably from the literature on LR-Regular and noncanonical parsing techniques:

Ada "is" a LR(2) snippet of the Ada syntax [START_REF] Ansi | Reference Manual for the Ada Programming Language ANSI/MIL-STD-1815A-1983[END_REF], pointed out by [START_REF] Baker | Extending lookahead for LR parsers[END_REF] and [START_REF] Boullier | Contribution à la construction automatique d'analyseurs lexicographiques et syntaxiques[END_REF];

Ada calls a non LR fragment of the Ada syntax, pointed out by [START_REF] Boullier | Contribution à la construction automatique d'analyseurs lexicographiques et syntaxiques[END_REF];

C++ qualified IDs a non LR-Regular portion of the C++ syntax (ISO, 1998);

Java modifiers a non LR excerpt of the Java syntax, which was detailed by [START_REF] Gosling | The Java TM Language Specification[END_REF] Pascal typed a LR(2) grammar for Pascal variable declarations that enforces type correctness, given by [START_REF] Tai | Noncanonical SLR(1) grammars[END_REF];

Set expressions a non LR grammar that distinguishes between arithmetic and set expressions, given by [START_REF] Čulik | LR-Regular grammars-an extension of LR( ) grammars[END_REF].

Results

We ran several conservative ambiguity detection tests on Basten's grammar collection and on our small collection. Table 4 shows the results of our micro-benchmarks, and Table 5 compiles the accuracy ratios we obtained.

Our small collection (a) contains only non-LALR(1) grammars, and as such the accuracy of the various tools can also be seen as an improvement ratio over LALR(1). The overall accuracy (b) score takes into account the complete collection of 52 unambiguous grammars using both our grammars and Basten's; 26 grammars are not LALR(1) in this full collection, giving rise to the overall improvement score (c).

The ability to freely specify lookahead lengths in a LR( ) parser improves over LALR(1) parsing, but is significantly less powerful than the methods that take an unbounded lookahead into account. An interesting point is that the results of our tool in LR( 1 The surface of each rectangle is roughly commensurate with its importance in the full collection of small grammars.

the two tools would obtain an overall 88% improvement rate, or 94% on our small collection only. Figure 6 sums up the grammar class inclusions for the various methods we presented, and attempts to render their relative importance on the complete collection of 100 small grammars.

Let us finally point out that a much larger grammar collection would be needed in order to obtain more trustworthy micro-benchmark result. Such results might still not be very significant for large, complex grammars with a lot of interaction, where the precision of a method seems to be much more important than for small grammars: for instance, our NU method performs as well with SLR(1) precision as with LR(1) precision on our 16 small grammars (Table 4), but the results of Table 3 demonstrate a significant improvement when employing LR(1) items on real grammars.

Addendum Most recently, in their latest implementation of their tool, Brabrand et al. offer now the possibility to automatically unfold a grammar at a given depth from user-provided opening and closing parentheses. Thanks to one or two levels of unfolding, they can analyze correctly all the grammars of Table 4 as unambiguous.

There is still interest in NU testing. Besides having a better time complexity, the class of grammars it defines is not subsumed by HVRU with unfolding: for instance, grammars 5 and 7 presented in Section 4.1.3 are NU(item 0 ) but not HVRU for any level of unfolding.

The two examples 6 and 7 introduced in Section 4.1.3 that showed that NU and HVRU were incomparable have practical counterparts in some existing grammars for programming languages:

• the already mentioned LR(2) excerpt of the YACC grammar is analyzed as potentially ambiguous by NU

- → | ; | , - → : , - → | (90-10-042)
unless we use item 2 approximations. Thus our algorithm does not bring any improvement over LR testing in this case.

• the following LR(2) grammar for expressions with casts, very similar to the grammar of Java casts discussed before, is reported as potentially ambiguous by Brabrand et al.'s tool for any amount of unfolding:

- → + | , - → | ( ) | ( ) (casts)
These two examples illustrate some typical constructs that either NU or HVRU cannot deal with, and further illustrate the interest of combining them.

Current Limitations

Our implementation is still a prototype. We describe several planned improvements (Sections 5.1 and 5.2), followed by a brief account on the difficulty of considering dynamic disambiguation filters and merge functions in the algorithm (Section 5.3).

Ambiguity Report

As mentioned in the beginning of Section 3, the ambiguity report returned by our tool is hard to interpret. A first solution, also advocated by [START_REF] Brabrand | Analyzing ambiguity of context-free grammars[END_REF], is to attempt to generate actual ambiguous inputs that exhibit the detected ambiguities. The ambiguity report would then comprise two parts, one for proven ambiguities with examples of input, and one for the potential ambiguities. The generation should only follow item pairs from which the potential ambiguities are reachable through ma relations, and stop whenever an ambiguity has been found or after having explored a given number of paths.

The good results [START_REF] Basten | The usability of ambiguity detection methods for contextfree grammars[END_REF] obtained with AMBER [START_REF] Schröer | AMBER, an ambiguity checker for context-free grammars[END_REF] on his set of small ambiguous grammars emphasizes the interest for a mixed strategy, where the paths to potential ambiguities in ma * could be employed to guide the generation of ambiguous sentential forms. The running time of AMBER on a full programming language grammar is currently rather prohibitive; running a generator on the portions of the grammar that might present an ambiguity according to our tool could improve it drastically. The initial experiments run by Basten in this direction are highly encouraging.

Displaying the (potentially) ambiguous paths in the grammar in a graphical form is a second possibility. This feature is implemented by ANTLRWorks, the development environment for ANTLR version 3 [START_REF] Parr | The Definitive ANTLR Reference: Building Domain-Specific Languages[END_REF].

≡

Running Time

The complexity of our algorithm is a square function of the grammar size. If, instead of item pairs, we considered deterministic states of items like LALR(1) does, the worst-case complexity would rise to an exponential function. Our algorithm is thus more robust. Nonetheless, practical computations seem likely to be faster with LALR(1) item sets: a study of LALR(1) parsers sizes by [START_REF] Purdom | The size of LALR(1) parsers[END_REF] showed that the size of the LALR(1) parser was usually a linear function of the of the grammar. Therefore, all hope of analyzing large GLR grammars-like the Cobol grammar recovered by [START_REF] Lämmel | Semi-automatic grammar recovery[END_REF]-is not lost.

The theory behind noncanonical LALR parsing [START_REF] Schmitz | Noncanonical LALR(1) parsing[END_REF] might translate into a special case of our algorithm for ambiguity detection, yielding the missing tradeoff between SLR(1) and LR(1) precision.

Dynamic Disambiguation Filters

In contrast with its treatment of static precedence and associativity directives, our tool does not ignore potential ambiguities when the user has declared a merge function that might solve the issue. The rationale is simple: we do not know whether the merge function will actually solve the ambiguity. Consider for instance the rules

- → | , - → | . ( 8 )
Our tool reports an ambiguity on the item pair ( -→ ⋅ , - → ⋅ ), and is quite right: the input is ambiguous. As shown in Figure 7, adding a merge function on the rules of would not resolve the ambiguity: the merge function should be written for .

If we consider arbitrary productions for , a merge function might be useful only if the languages of the alternatives for are not disjoint. We could thus improve our tool to detect some useless merge declarations. On the other hand, if the two languages are not equivalent, then there are cases where a merge function is needed on -or even at a higher level. Ensuring equivalence is difficult, but could be attempted in some decidable cases, namely when we can detect that the languages of the alternatives of are finite or regular, or using bisimulation equivalence [START_REF] Caucal | Graphes canoniques de graphes algébriques[END_REF].

Conclusions

The paper reports on an ambiguity detection tool. In spite of its experimental state, the tool has been successfully used on a very difficult portion of the Stan-

  datatype 'a option = NONE | SOME of 'a fun filter pred l = let fun filterP (x :: r , l ) = case (pred x) of SOME y => filterP(r, y::l) | NONE => filterP(r, l ) | filterP ([], l ) = rev l in filterP ( l , []) end

of

  SOME y => filterP(r, y::l) | NONE => filterP(r, l) Attempted parse when reducing.of SOME y => filterP(r, y::l) | NONE => filterP(r, l) Correct parse tree when shifting. | NONE => filterP(r, l) | filterP ([], l ) = rev l Correct parse tree when reducing. | NONE => filterP(r, l) | filterP ([], l ) = rev l

Figure 2 :

 2 Figure 2: Partial parse trees corresponding to the two occurrences of the conflict in Example 1.

Figure 3 :

 3 Figure 3: The shared parse forest for the input of Example 2.

Figure 4 :

 4 Figure 4: The shared parse forest for the input of Example 3.

Figure 5 :

 5 Figure 5: Two equivalent positions under the LR(0) item approximation, corresponding to the single item [⟨sfvalbind ⟩ -→ vid ⟨atpats⟩ ⋅ = ⟨exp⟩].

  ) NFA. Let | | denote the size of the context-free grammar , i.e. the sum of the length of all the rules right parts, and | | denote the number of rules; then, in the LR(0) case, the algorithm time and space complexity are bounded by ((| | | |) 2 ).

  98-05-030 a non LR excerpt of the Tiger syntax; 98-08-215 a LR(2) grammar; 03-02-124 a LR(2) excerpt of the C# grammar; 03-09-027 a LR(2) grammar; 03-09-081 a LR(3) grammar; 05-03-114 a LR(2) grammar.

  in their Sections 19.1.2 and 19.1.3; Java names a non LR excerpt given in their Section 19.1.1; Java arrays a LR(2) excerpt given in their Section 19.1.4; Java casts a LR(2) excerpt given in their Section 19.1.5;

Figure 6 :

 6 Figure 6: Grammar classes inclusions of various context-free grammar classes.The surface of each rectangle is roughly commensurate with its importance in the full collection of small grammars.

Figure 7 :

 7 Figure 7: The shared parse forest for input with grammar 8 .

Table 1 :

 1 Reported potential ambiguities in the comparison grammars.

	Grammar actual class LALR(1) HVRU NU(item 0 )
	3	LR(2 )	1	0	0
	5	non-LRR	1	1	0
	6	non-LRR	6	0	9
	7	LR(0)	0	1	0
	Table 2: Reported potential ambiguities in the RNA grammars discussed by
	Reeder et al. (2005).
	Grammar actual class LALR(1) HVRU NU(item 1 )
	RNA 1	ambiguous	30	6	14
	RNA 2	ambiguous	33	7	13
	RNA 3	non-LRR	4	0	2
	RNA 4	SLR(1)	0	0	0
	RNA 5	SLR(1)	0	0	0
	RNA 6	LALR(1)	0	0	0
	RNA 7	non-LRR	5	0	3
	RNA 8	LALR(1)	0	0	0
	that our method finds erroneously ambiguous. Conversely, grammar 7 with
	rules
		-→	, -→	|	( 7 )
	is a LR(0) grammar, and the test of Brabrand et al. finds it horizontally am-
	biguous and not vertically ambiguous.
	Table

Table 3 :

 3 Number of initial LR(0) conflicting pairs remaining with the LR, LRR and NU tests employing successively LR(0), SLR(1), LALR(1), and LR(1) precision.

	Precision		LR(0)			SLR(1)		LALR(1)		LR(1)
	Method	LR LRR NU	LR LRR NU	LR	LR LRR NU
	Pascal	119	55 55	5	5	5	1	1	1	1
	Mini C	153	11 10	5	5	4	1	1	1	1
	ANSI C	261	13	2	13	13	2	1	1	1	1
	ANSI C'	265 117 106	22	22 11	9	9	-	-
	Standard ML	306 163 158	130 129 124	109	109 107 107
	Small Elsa C++	509 285 239	25	22 22	24	24	-	-
	Elsa C++	973 560 560	61	58 58	53	-	-	-

Table 4 :

 4 Number of conflicts obtained with Bison, Brabrand et al.'s tool, and our tool in LRR and NU modes with various precision settings.

	Method	actual	LR	HVRU	LRR		NU
	Precision	class LALR(1) ≥LR(0) LR(1) LR(0) SLR(1) LR(1)
	90-10-042	LR(2)	2	0	14	7	7	6
	98-05-030	non LR	1	10	26	0	0	0
	98-08-215	LR(2)	1	0	0	0	0	0
	03-02-124	LR(2)	1	0	0	0	0	0
	03-09-027	LR(2)	2	0	0	0	0	0
	03-09-081	LR(3)	2	0	0	0	0	0
	05-03-114	LR(2)	1	0	0	0	0	0
	Ada "is"	LR(2)	1	0	0	0	0	0
	Ada calls	non-LR	1	0	0	1	0	0
	C++ qualified IDs non-LRR	1	5	21	0	0	0
	Java modifiers	non-LR	31	0	0	3	0	0
	Java names	non-LR	1	0	0	0	0	0
	Java arrays	LR(2)	1	0	0	0	0	0
	Java casts	LR(2)	1	0	0	0	0	0
	Pascal typed	LR(2)	1	0	0	0	0	0
	Set expressions	non-LR	8	19	119	2	2	2

Table 5 :

 5 Accuracy ratios of each method (a) on our set of 16 small grammars, (b) on the complete set of 52 unambiguous small grammars, and (c) on the set of 26 non-LALR(1) small grammars.

	Method	LR		HVRU	LRR		NU
	Precision	LALR(1) LR( ) ≥LR(0) LR(1) LR(0) SLR(1) LR(1)
	(a) Accuracy/improvement	0%	62%	81%	75%	75%	87%	87%
	(b) Overall accuracy	50%	69%	69%	75%	65%	75%	87%
	(c) Overall improvement	0%	42%	69%	50%	58%	65%	73%

Some deterministic parsing algorithms-LR-Regular[START_REF] Čulik | LR-Regular grammars-an extension of LR( ) grammars[END_REF][START_REF] Baker | Extending lookahead for LR parsers[END_REF][START_REF] Boullier | Contribution à la construction automatique d'analyseurs lexicographiques et syntaxiques[END_REF], noncanonical[START_REF] Szymanski | Noncanonical extensions of bottomup parsing techniques[END_REF][START_REF] Tai | Noncanonical SLR(1) grammars[END_REF][START_REF] Schmitz | Noncanonical LALR(1) parsing[END_REF], or LL-Regular[START_REF] Poplawski | On LL-Regular grammars[END_REF][START_REF] Parr | The Definitive ANTLR Reference: Building Domain-Specific Languages[END_REF]-albeit perhaps less known, are able to exploit unbounded lookahead lengths. Our ambiguity detection algorithm employs similar principles.

Since this occurs as soon as we find a mac relation that reaches the same item twice, the mar relation and the boolean flag described in the general algorithm[START_REF] Schmitz | Conservative ambiguity detection in context-free grammars[END_REF] are not needed.

The names xx-xx-xxx are the message identifiers on the archive, respectively available at http://compilers.iecc.com/comparch/article/xx-xx-xxx.

Acknowledgements The work reported in this article was conducted at the Laboratoire I3S, Université de Nice -Sophia Antipolis & CNRS, France.

The author gratefully acknowledges the help received from Bas Basten with his grammar collection and from Claus Brabrand and Anders Møller with their ambiguity detection tool.

The author also thanks Jacques Farré for his help in the preparation of this paper and Sébastien Verel for granting him access to a fast computer.

dard ML grammar. The tool also improves on the dreaded LALR(1) conflicts report, albeit at a much higher computational price.

We hope that the need for such a tool, the results obtained with this first implementation, and the solutions described for the current limitations will encourage the investigation of better ambiguity detection techniques. The integration of our method with the one designed by Brabrand et al. is another promising solution.