Bilal Berjawi

Fabien Duchateau

Franck Favetta

Maryvonne Miquel

Robert Laurini

PABench: Designing a Taxonomy and Implementing a Benchmark for Spatial Entity Matching

Keywords: Benchmark, Location-based services composition, Location-based services interoperability, Spatial entity matching, Taxonomy

The tremendous increase of data sources containing spatial information is bound up with the diversity of geospatial applications such as location-based services (LBS) and global positioning systems. LBS providers use maps to locate spatial entities referring to points of interest (POI), for instance restaurants or locations of events. In our study, we specifically focus on places that tourists can get through LBS. The multiplication of these providers has an impact on the quality of data: spatial entities referring to the same POI may include spatial and terminological properties with incomplete, inconsistent, inaccurate or even wrong data. Thus, entity matching approaches have been proposed to discover correspondences between spatial entities, and experimental validations are traditionally performed to demonstrate the performance of these approaches in terms of effectiveness and efficiency. However, the datasets used in these experiments are rarely available, thus limiting their reuse and a fair comparison between the proposed approaches. This paper introduces PABench, a benchmark for spatial entity matching, which is available for researchers to assess their algorithms. Our benchmark includes a taxonomy of observed differences, inconsistencies and errors, which enables the characterization of different LBS providers. PABench can provide a complete and accurate evaluation of the different aspects of spatial entity matching approaches, and also facilitate an understanding of their weaknesses and abilities with respect to spatial integration. This paper provides a conceptual platform to enable LBS interoperability.

I. INTRODUCTION

With the proliferation of LBS and the increasing amount of geographic data, many issues arise related to the integration of several sources of spatial data. This integration is necessary in order to update information that changes daily [START_REF] Gregory | Time-variant gis databases of changing historical administrative boundaries: A european comparison[END_REF] or to produce more complete and accurate information [START_REF] Cobb | Fuzzy spatial relationship refinements based on minimum bounding rectangle variations[END_REF]. LBS are daily used in various applications, and cartographic providers (e.g., Google Maps, Bing Maps, MapQuest) play an essential role in offering POIs such as restaurants, hotels and tourist places. A POI can be defined as a geographic object that has a point geometric shape. A POI has spatial attributes, longitude and latitude, and terminological (non-spatial) attributes such as name and type (e.g., restaurant, hotel). Some providers may supply additional terminological attributes such as address, phone number, web site, customers' ratings, etc. Due to lack of completeness, noise, inaccurate and contradictory data, it is interesting to propose solutions for detecting corresponding entities (i.e., which refer to the same POI) as given from different providers. This challenge aims at improving the quality and the relevance of information, which has a significant impact in tourist applications.

Geospatial integration has been widely studied under the term "map conflation" where two whole maps are integrated. Integration of maps consists of identifying the corresponding entities and fusing them [START_REF] Casado | Some basic mathematical constraints for the geometric conflation problem[END_REF]. Ruiz et al. present a wide description of the art with respect to map conflation [START_REF] Ruiz | Digital map conflation: a review of the process and a proposal for classification[END_REF]. The authors describe existing works in map conflation regarding their formats (raster and vector) and their criteria such as spatial data, terminological data and topological relationships between entities. Some works have been proposed in map conflation using punctual entities [START_REF] Saalfeld | A fast rubber-sheeting transformation using simplicial coordinates[END_REF][6] [START_REF] Volz | An iterative approach for matching multiple representations of street data[END_REF], linear entities [START_REF] Saalfeld | Conflation automated map compilation[END_REF] [START_REF] Doytsher | A rubber sheeting algorithm for non-rectangular maps[END_REF][10] and polygonal entities [START_REF] Arkin | An efficiently computable metric for comparing polygonal shapes[END_REF][12] [START_REF] Masuyama | Methods for detecting apparent differences between spatial tessellations at different time points[END_REF]. Thakkar et al. propose a tool to assess the quality of geospatial data sources [START_REF] Thakkar | Quality-driven geospatial data integration[END_REF]. It utilizes the information from geospatial data sources with known quality to estimate the quality of geospatial data sources with unknown quality. In the last decade, the integration problem mainly refers to the "entity matching" research domain, enhanced by a spatial aspect. The discovery of corresponding entities is performed either by exploiting only spatial information [START_REF] Safra | Locationbased algorithms for finding sets of corresponding objects over several geo-spatial data sets[END_REF] or by computing and combining terminological similarities for selected attributes (e.g., name, type) [START_REF] Raimond | Data matching -a matter of belief[END_REF] [START_REF] Karam | Integration of similar location based services proposed by several providers[END_REF]. Machine learning algorithms may be applied to tune the parameters (e.g., weights) of a matching process [START_REF] Sehgal | Entity resolution in geospatial data integration[END_REF]. When corresponding entities have been detected, an interesting use case aims at displaying a merged entity, i.e., to use a crafted algorithm to fuse the attributes' values of these corresponding entities. Such merging algorithms are not 100% confident. For instance, two corresponding entities may have a different location and the algorithm needs to determine the correct position. Similarly, the names or the phone numbers of two corresponding entities may differ, and the choice of the correct values relies on the merging algorithm. A merged entity may therefore include at different levels some uncertainties, which have to be presented to end-users [START_REF] Berjawi | Representing uncertainty in visual integration[END_REF].

Unfortunately, it is impossible to have a fair evaluation and comparison between existing approaches due to the absence of benchmarks. Our objective is to design such a benchmarking system, called PABench (POI Alignment Benchmark) to compare the existing spatial entity matching approaches in order to improve them or to build a better one. First, it is important to find out how the corresponding entities differ between each other in order to understand how they can be integrated. To do so, we formalize a taxonomy to distinguish the differences that may occur within the entity set of one single provider, denoted as Intra-Difference class, and the differences between the entity sets of several providers, denoted as Inter-Difference class. The former class helps evaluate the quality of the entity set of one provider (e.g., complete information, redundancies), while the latter helps evaluate the matching between the entity sets of several providers. This taxonomy is useful to produce statistics about the providers' datasets. The next step is to create a benchmark based on the characterization of the taxonomy to understand the weaknesses and strengths of spatial entity matching approaches.

Our contributions can be summarized as follows: (i) propose a model of LBS, (ii) construct the taxonomy and understand how it impacts the results' quality of a spatial entity matching system, (iii) create a benchmark that serves in evaluating and comparing the spatial entity matching approaches [START_REF]PABench[END_REF].

The paper is organized as follows. In Section II, related work is discussed. The taxonomy of differences is given in Section III. PABench is presented in Section IV. The construction of datasets is given in Section V and a use case is provided in Section VI. Finally, Section VII concludes the paper and outlines future work.

II. RELATED WORK

In this section, we present existing benchmarks in data integration.

In ontology matching, the objective is to discover semantic correspondences between concepts and properties of different ontologies [START_REF] Euzenat | Ontology matching[END_REF]. Ontology alignment researchers have designed Ontology Alignment Evaluation Initiative (OAEI) [START_REF]Ontology Alignment Evaluation Initiative[END_REF] to compare ontology alignment tools. The OAEI datasets fulfill various criteria. For instance, the benchmark dataset gathers many ontologies in which a specific type of information has been altered (modifications, deletions, etc.). Consequently, it aims at detecting the weaknesses of a tool according to available information. Other datasets might be very specific like the Food and Agriculture Organization ontologies, which usually require external resources such as dictionaries to obtain acceptable results. In 2013, the initial datasets have been extended with synthetic ones [START_REF] Euzenat | Ontology matching benchmarks: generation, stability, and discriminability[END_REF].

Schema matching and mapping can be defined as the discovery of correspondences between schema elements as well as the mapping functions to transform source instances into target instances [START_REF] Bellahsene | Schema Matching and Mapping[END_REF]. The community has designed benchmarks for evaluating these two tasks. XBenchMatch enables the assessment of schema matching tools [START_REF] Duchateau | Designing a benchmark for the assessment of schema matching tools[END_REF]. It includes a classification of task-oriented datasets and new metrics for computing the post-match effort. STBenchmark aims at evaluating the quality of the mapping functions and their execution time [START_REF] Alexe | Stbenchmark: towards a benchmark for mapping systems[END_REF]. Datasets are gathered according to common transformations (e.g., copying, flattening) but they can be enriched using instance generators, which can be tuned with configuration parameters (e.g., kinds of join, nesting levels).

The entity matching task, which is directly related to spatial entity matching, consists of discovering correspondences between equivalent objects. It also benefits from two benchmarks. The former proposes a set of four datasets about ecommerce and scientific publications [START_REF] Köpcke | Evaluation of entity resolution approaches on real-world match problems[END_REF]. These static datasets were used to compare entity matching tools. On the other hand, EMBench is based on importing existing entities (e.g., from Linked Open Data) and applying modifiers to their features (e.g., abbreviation, synonyms) [START_REF] Ioannou | On generating benchmark data for entity matching[END_REF]. These changes generate a set of modified entities, which form an entity matching dataset when grouped with the original entities. Although these two entity matching benchmarks are useful in most contexts, they are insufficient when dealing with spatial matching.

To the best of our knowledge, there is no benchmark for evaluating spatial entity matching approaches. Kang et al. propose a tool to detect the corresponding spatial entities [START_REF] Kang | Geoddupe: A novel interface for interactive entity resolution in geospatial data[END_REF]. They take two sources of entities as input, the potentially corresponding entity pairs being automatically detected based on a specified similarity measure. Then, the user has to make a decision for each pair to be considered as corresponding or not. This tool may be interesting to create a training dataset but it is not enough for a benchmark. Beeri et al. implemented a random-dataset generator to evaluate their spatial entity matching approach [START_REF] Beeri | Finding corresponding objects when integrating several geo-spatial datasets[END_REF]. They generate two datasets of spatial entities in which some entities are corresponding. Unfortunately, generated entities are described only by spatial information (longitude and latitude) because their proposed matching approach exploits only the spatial information to detect the correspondences. Otherwise, the datasets used in the spatial entity matching papers are not made fully available, for instance because of confidentiality issues. A few attempts are available, such as a dataset about restaurants [START_REF]Restaurants' dataset[END_REF]. Yet, they cannot be exploited for various reasons. Some of them are not challenging (e.g., a simple equality metric applied to the phone numbers in the restaurant dataset discovers all the correct corresponding entities). In addition, a specific dataset may be required, for instance to include all POI types (e.g., restaurants, museums, mountains) or all entities from a given area. This lack of benchmark does not facilitate a fair and accurate comparison of the different spatial matching approaches. We also argue that the properties of a dataset are useful, both for understanding why a spatial entity matching approach is (not) effective, and for using appropriate training data when needed.

III. TAXONOMY

In this section, we present a taxonomy to characterize the differences between the LBS providers. We start by introducing preliminary definitions that describe a model of LBS providers.

A. Preliminary definitions

It is necessary to understand the context of the LBS in order to construct a process to integrate them. In this section we illustrate a model that describes the LBS context of multi-provider.

Definition 1: Point of Interest (POI)

A POI is a geographical object described by a set of properties. Among these properties, there is a name, a type (e.g., restaurant, castle), a location (positioning coordinates) and a geometric shape (e.g., point, line, polygon). It is defined by the tuple: P OI = (name, type, coordinates, shape) For example, the tuple ET below represents the Eiffel Tower POI: ET = (Eiffel Tower, Tourist, (48.858439, 2.294474), Point)

We distinguish between large POI and small POI relative to the POI area in the real-world. For example, a pub is a small POI while a park is a large POI. Let us consider the set P = {p 1 , ..., p q } that contains all the POIs of the real world where q is the number of POIs. Each LBS provider offers a set of entities that refer to a subset of existing POIs. Currently, the entities are represented with a point geometrical shape. Regarding the entities that refer to POIs with large areas, they are approximated by points such as computing their center of gravity [START_REF] Beeri | Finding corresponding objects when integrating several geo-spatial datasets[END_REF]. The entities offered by a provider are derived from a specific schema of that provider.

Definition 2: Schema of provider The schema S k describes the structure of entities offered by the provider k. It is defined by:

S k = I k ∪ L k ∪ A k ∪ B k
where

• I k = {id k } is an internal identifier attribute that
represents a given entity for the provider k.

• L k = {LONGITUDE k .label, LATITUDE k .label} is a
pair of spatial attributes standing for the spatial information.

• A k = {NAME k .label, POITYPE k .
label} is a pair of terminological attributes that are mandatory. We call them primary attributes because they exist in the schemas of all providers and always have values.

• B k = attB 1
k .label, ..., attB r k .label is another set of terminological attributes that are optionally provided with r = |B k |. We call them secondary attributes because they may be either missed from some schemas or have null values.

Hypothetically, a schema of any provider k includes at least all attributes in I k ∪ L k ∪ A k . We note att i k any attribute of the schema S k . The abstract data type of att i k , denoted as att i k .type, may have one of the following data types: string, number, array or associative array. Note that a schema may be static or dynamic. A static schema has fixed labels and structures, while for a dynamic schema, labels and structures can be modified. As an example, the provider OpenStreetMap [START_REF]OpenStreetMap[END_REF] has a dynamic schema in which the user can add new attributes for some entities. In contrast, GoogleMap [START_REF]Google Maps[END_REF] has a static schema, so that the number and the labels of the attributes are common for all the entities. The entity set of a provider k is denoted by E k = {e 1 , ..., e n } where n is the number of entities. where r is the number of secondary attributes of the schema S k . Table I shows an example of two entities x and y offered by two different providers that represent the POI ET (Eiffel Tower) with two different schemas. We denote E = m k=1 E k , the union set of m providers' entities sets.

Definition 4: Association function f

The association function f is defined by:

f :E → P e → f (e) = p
such that e ∈ E refers to p. For example, the entity x of Table I refers to the POI ET (Eiffel Tower) and f (x) = ET .

Definition 5: Corresponding entities

Two entities e 1 ∈ E 1 and e 2 ∈ E 2 are corresponding entities, denoted e 1 ≡ e 2 , iff

∃ p ∈ P\f (e 1 ) = f (e 2 ) = p
For example, the two entities x and y of Table I are corresponding entities (x ≡ y) because they refer to the same POI ET (Eiffel Tower). Definition 6: Corresponding attributes Two attributes att i 1 ∈ S 1 and att j 2 ∈ S 2 are two corresponding attributes, denoted att i 1 ≡ att j 2 , iff they represent the same concept.

In the literature of schema matching, the correspondences between attributes are represented by a relationship [START_REF] Bellahsene | Schema Matching and Mapping[END_REF] such as equivalence, overlap, disjointness, exclusion. But in the context of LBS providers, we only consider the equivalence relationship.

In the next section, we use the above definitions to introduce the taxonomy of differences.

B. Taxonomy of differences

In this section, we propose a formalization of the various differences that may arise between the entities of two providers. To illustrate the comparison between providers, let us consider E 1 and E 2 as entity sets of two LBS providers.

Let S 1 = I 1 ∪ L 1 ∪ A 1 ∪ B 1 and S 2 = I 2 ∪ L 2 ∪ A 2 ∪ B 2
be the schemas of E 1 and E 2 respectively. Also, consider the POI p ∈ P and two corresponding entities e 1 ∈ E 1 and e 2 ∈ E 2 that refer to p (i.e., e 1 ≡ e 2 ).

The potentially corresponding entities of several sets will be compared depending on four levels: 1) schema, 2) terminology, 3) spatial and 4) entities' availability.

1) Schema Differences:

This level explains the heterogeneity between distinct schemas where two differences are distinguished. Generally, differences between schemas involve two providers, i.e., Inter-Difference. In the case of a provider with a dynamic schema, differences may be classified as Intra-Difference.

Attribute Heterogeneity:

The attribute heterogeneity consists of two corresponding attributes belonging to two distinct schemas and have different labels or different abstract data types. In Table I, the attribute

att i 1 ≡ att j 2 ∧ att i 1 .label = att j 2 .label ∨ att i 1 .type = att j 2 .

type

Different Structures: Schemas may have various structures. One attribute of one schema may correspond to two or more attributes of another schema. Returning to Table I, the address is represented by three attributes Locality, PostalCode and AddressLine in the schema of the provider 1 while the attribute formatted address in the schema of the provider 2 represents the full address. That is, a concept is described by one attribute of the schema S 1 and by two or more attributes of the schema S 2 , or vice versa.

att i 1 ≡ (att 1 2 , att 2 2 , . . .) ∨ (att 1 1 , att 2 1 , ...) ≡ att j 2
There are complex correspondences between the structures of the schemas. For instance, more than one attribute of a schema may correspond to more than one attribute of another (i.e., [n:m] correspondences). We do not consider the complex correspondences in this paper since the schemas in the context of LBS are simple.

2) Terminological Differences: This level is related to the heterogeneity of values for primary and secondary terminological attributes of two corresponding entities.

Different Data:

Two corresponding entities have different values for their corresponding terminological attributes (primary or secondary). e 1 and e 2 have different data iff

∃ att x 1 ∈ A 1 ∪ B 1 , ∃ att y 2 ∈ A 2 ∪ B 2 \ e 1 ≡ e 2 ∧ (e 1 .att x
1 ≡ e 2 .att y 2 ) ∧ (e 1 .att x 1 .val = e 2 .att y 2 .val) Note that the degree of difference between the data varies. This variation may be classified as semantic (SEM) or syntactic (SYN). The former consists of two corresponding attributes that have different values but are based on the same concept (e.g., eat-drink and restaurant are two POI types that have the same meaning). The latter is about the syntax of corresponding attributes' values. They are a consequence of the different ways that a value can be written in real life, without any alteration of its meaning, or a result of human errors (i.e., misspellings, word permutations, aliases, different standards, acronyms, abbreviations and multilingualism). In Table I, the type of the entity x is 7999 while it is establishment for the entity y. Different Data (SEM and SYN) is classified as Inter-Difference.

Missing Data (MD):

Two corresponding entities having a feature that is described by one entity and missed by the other. In Table I, the website is missing from the entity x while it is given by the entity y. This difference is classified as Inter-Difference. e 1 and e 2 have missing data iff

∃ att x 1 ∈ A 1 ∪ B 1 , ∃ att y 2 ∈ A 2 ∪ B 2 \ (att x 1 ≡ att y 2 ∧ (e 1 .att x 1 .val = N U LL ∨ e 2 .att y 2 .val = N U LL)) ∨ ∃ att x 1 ∈ A 1 ∪ B 1 , ∀ att y 2 ∈ A 2 ∪ B 2 \ (att x 1 ≡ att y 2 )
Similar Data: It consists of two entities that have similar values for terminological attributes but refer to two distinct POIs of the same type. Consider two POIs p ∈ P and p ∈ P of the same type, and two entities e ∈ E and e ∈ E that refer to p and p respectively. If e and e have similar values for any terminological attributes, then the difference between e and e is denoted as similar data. Usually, the Similar Data difference appears when we have two or more branches of the same organization. Entities that represent these branches are of the same type, have similar terminological values (e.g., place name), located in different areas and not corresponding to each other because each branch is a distinct POI. This differences is classified as Similar Data is classified as Intra-Difference and Inter-Difference.

3) Spatial Differences: At this level, we investigate the problem of positioning between the corresponding entities. Three differences can be distinguished.

Different Locations (DL):

Two corresponding entities have different values for their corresponding spatial attributes. The two entities of

Superposition:

This consists of two entities that have the same locations but refer to two distinct POIs of the same type and it is classified as Intra-Difference and Inter-Difference. Usually, this case appears in shopping centers where two POIs of the same type are located one above the other on two different floors. Consider two POIs p ∈ P and p ∈ P of the same type, and two entities e ∈ E and e ∈ E that refer to p and p respectively. If e and e have the same location, then the difference between e and e is denoted as superposition. The entity's availability category takes into account errors that can be found in the entity set of a provider. Two differences can be distinguished at this level.

Not Found Entity:

This case, classified as Inter-Difference, consists of a POI that is given by one provider but not by the other. Considering the POI p ∈ P, p is a Not found POI iff

∃ e 1 ∈ E 1 , ∀ e 2 ∈ E 2 \f (e 1 ) = p ∧ f (e 2 ) = p
Duplicate Entities: This case, classified as Intra-Difference, corresponds to two entities of the same provider that refer to the same POI. Consider two entities e 1 ∈ E 1 and e 1 ∈ E 1 , e 1 and e 1 are two duplicate entities iff ∃ p ∈ P\ f (e 1 ) = f e 1 = p Although the differences described in the taxonomy are elementary, the detection of the corresponding entities requires some hard work because a combination of differences may occur when comparing two entities. For instance, the two entities x and y of Table I are two corresponding entities with a combination of four differences, namely 1) Attribute Heterogeneity, 2) Different Structure, 3) Syntactic Different Data (SYN) and 4) Different Locations (DL).

IV. BENCHMARK

The taxonomy of differences is useful to get statistics about LBS providers and to understand how they can be integrated. Also, it serves to create a benchmark that evaluates the performance of spatial entity matching approaches and to build a characterized dataset that serves for machine learning purposes. In this section we describe PABench [START_REF]PABench[END_REF] based on this taxonomy.

A. Overview of the matching process

In general, the data integration process consists of three consecutive phases namely 1) schema/ontology matching, 2) entity matching and 3) entity merging or fusion. The schema matching task helps finding corresponding attributes between two schemas in order to compare their values later in the entity matching task. It produces an alignment between the corresponding attributes accompanied by a transformation function such as combination, split, etc. A schema matching approach must be able to handle the differences denoted in the schema category namely Attribute Heterogeneity and Different structures. In the context of LBS, the schema matching of providers can be done manually since their schemas are small and simple, so that there is no need for semi-or fullyautomatic approaches to handle the schema matching task. Secondly, (spatial) entity matching approaches are used to find corresponding entities in several datasets to merge them together. It takes as input the datasets that need to be merged and the alignment of their schemas produced by the schema matching task. Entity matching can be done by computing a similarity score between each pair of entities. Then, a matching approach considers a pair of entities as corresponding if its similarity score is higher than a given threshold [START_REF] Madhavan | Generic schema matching with cupid[END_REF], or produces a list of pairs of entities ranked according to their similarity score. Concerning spatial entity matching systems, they measure the degree of similarity between entities using various techniques such as Euclidean distance between entities' locations, semantic equivalence and syntactic comparison of terminological information. These measures serve to compute a score that indicates their belief that two entities correspond. Finally, the entity merging phase takes as input the result of the entity matching task in order to fuse the corresponding entities. How the entities are merged depends on how these entities will be used, it may be done by a simple combination of values or based on specific rules in a given context. In our context, we intend to consider the tourist rules to merge the spatial entities. Note that the schema matching and the entity merging are no longer discussed in this paper; next we focus on the evaluation of spatial entity matching approaches.

To evaluate the performance and the results' quality of a spatial entity matching system, consider two datasets, namely source and target, for which a list of correct correspondences, called ground truth, is known in advance. For each entity in the source dataset, the matching system will try to find the corresponding entity from the target dataset. Thus, correspondences returned by the matching system are compared to the ground truth correspondences in order to measure how successfully the matching system detects the expected answer.

B. Benchmark construction

PABench has been constructed based on the differences defined in the taxonomy. Recall that a spatial entity consists of spatial and terminological (primary and secondary) information and refers to a real world POI. Deciding whether two spatial entities correspond is a challenging task due to the differences that occur between them. As previously mentioned, two corresponding entities being compared may have a combination of differences where each combination is a distinct situation of differences. To understand the weaknesses and strong points of an entity spatial matching system, the evaluation must be characterized according to the situations of differences that may occur between entities. In other words, it is required to evaluate a spatial entity matching system based on each situation of differences.

The possible situations of differences are computed based on the taxonomy of differences with respect to the entity matching task. Since the entity matching goal is to detect the corresponding entities, only the differences concerning corresponding entities are considered, namely Different Locations (DL) and Equipollent Positions (EP) from the spatial category and Missing Data (MD), Semantic Different Data (SEM) and Syntactic Different Data (SYN) from the terminological category. Superposition, Similar Data and Not Found Entity differences may be used to add noise entities (see below) when comparing the source and target datasets. Finally, Duplicate Entities must be pre-handled before the entity matching task using deduplication techniques to ensure the quality of used datasets.

Spatial information is only expressed by an entity's location, it may have zero (i.e., no difference) or only one difference in the spatial category differences. The set of spatial differences S dif is given by: S dif = {∅, DL, EP } Primary terminological information is expressed by an entity's name and type, it may have zero, one (i.e., at least one attribute has the difference) or two differences of the terminological category differences. The Missing Data (MD) difference cannot be considered because the primary terminological attributes are always provided and have values (see Section III-A). The set of primary terminological differences P T dif is given by: P T dif = {∅, SEM, SY N, (SEM, SY N )} Secondary terminological information varies from one provider to another, it may have zero, one (i.e., at least one attribute has the difference), two (i.e., each difference appears at least once) or three differences of the terminological category differences. The set of secondary terminological differences ST dif is given by: ST dif ={∅, SEM, SY N, M D, (SEM, SY N, M D) , (SEM, SY N ) , (SEM, M D) , (SY N, M D)} Let Situations dif be the set of all possible combinations of differences that may occur between two corresponding entities at all levels (spatial, primary terminological and secondary terminological)

Situations dif ={a, b, c \ a ∈ S dif, b ∈ P T dif, c ∈ ST dif }
where

|Situations dif | = 3 × 4 × 8 = 96
Returning to Table I, the two corresponding entities x and y have a combination of differences. For spatial information they have Different Locations (spatial coordinates), for primary terminological information they have Syntactic Different Data (name, type) and for secondary terminological information they have Syntactic Different Data (phone, address) and Missing Data (website). The situation s ∈ Situations dif between x and y is given by s = {DL, SY N, (SY N, M D)}.

To guarantee that the situations have no redundancy, each situation s ∈ Situations dif must be unique and exclusive, in the sense that the situations do not share any relation between them such as intersection, inclusion, etc. Thus, our benchmark consists of comparing a source dataset with a target dataset in which the corresponding entities have a specific situation of differences. If the correct answer (represented by the ground truth) is returned by a matching approach, it means that it is able to deal with the given situation.

Definition 7: TestCase For each situation s ∈ Situations dif , we define a test case that consists of a source dataset

E S ⊂ E (E = m k=1 E k ), a
target dataset E T ⊂ E and a ground truth between both source and target datasets.

T estCase(s) = (E S , E T , groundT ruth)
Noise entities may be added to E S and E T . A noise entity is an entity that exists in one dataset and does not have any correspondence in the other dataset. The goal of adding noise entities is to explain whether a matching approach is able to avoid detecting two non-corresponding entities even if they have near locations or similar information. Noise entities should contain entities with Not Found Entity, Similar Data and Superposition differences. Concerning the Not found Entity difference, it can be easily detected from the real entities of LBS providers. But Similar Data and Superposition are hard to detect, in this case we intend to automatically generate entities with such differences. These test cases allow us to find the situations of differences that a matching approach is able to handle and to what degree this handling is possible in order to differentiate it from other similar approaches.

C. Quality measure and impact of differences

Results' quality of a matching system is measured by the standard performance measures that come from the information retrieval domain, precision, recall and F-measure [START_REF] Rijsbergen | Information Retrieval[END_REF]. These measures evaluate the performance of a matching system by comparing its results to ground truth's results. Also, they help to understand weaknesses and strengths of a matching approach for each test case. Table II classifies the contingency of evaluation measures' base. Precision calculates the proportion of correct correspondences detected by the matching system among all detected correspondences. Using the notations of Table II, the precision is given by formula [START_REF] Gregory | Time-variant gis databases of changing historical administrative boundaries: A european comparison[END_REF]. A 100% precision means that all correspondences detected by the matching system are true.

precision =

T P T P + F P

Recall computes the proportion of correct correspondences detected by the matching system among all correct correspondences. The recall is given by formula [START_REF] Cobb | Fuzzy spatial relationship refinements based on minimum bounding rectangle variations[END_REF]. A 100% recall means that all correct correspondences have been found by the matching system.

recall = T P T P + F N (2)
F-measure is a trade off between precision and recall and it is calculated with the formula (3). The β parameter of formula (3) regulates the respective influence of precision and recall (β ∈ R + ). It is often set to 1 to give the same weight to these two evaluation measures.

F -measure (β) = β 2 + 1 × precision × recall (β 2 × precision) + recall (3)
It is important to analyze how the differences of the taxonomy impact these measures in order to discover the weaknesses and the strengths of an approach. Concerning the Attribute Heterogeneity, Different Structure and Duplicate Entities differences, they are pre-handled before launching the spatial entity matching process. Different Data (SEM and SYN), Missing Data, Different Locations and Equipollent Positions must be addressed through the matching system. They impose obstacles that may prevent a matching system from detecting the correct corresponding entities. Hence, if a matching approach fails to overcome those obstacles, True Positive (TP) decreases, False Negative (FN) increases and recall decreases. Concerning Superposition and Similar Data, two distinct entities with the same location or with similar data may be detected as corresponding. These differences increase False Positive (FP) and precision decreases. The Not Found Entity concerns a POI that is represented by one provider and not by the other, that means the entity of the first provider does not correspond to any of the entities of the second provider. But it risks a situation where a matching approach detects a correspondence for an entity of this difference, which increases FP and precision decreases. Also, this difference impacts the entity merging phase because as long as the number of available entities is small, we cannot ensure the correctness of information. In the case of Duplicate Entities, a matching approach may detect the same correspondence twice. This case will increase TP leading to a wrong precision value. That is why it is important to verify the quality of providers' datasets before starting the matching process using deduplication techniques. Table III summarizes the taxonomy of differences and their impacts on the quality measures.

V. DATASETS A tool that consists of two modules has been implemented in order to generate the datasets of test cases. The first module, called GeoBench [START_REF] Morana | Geobench: a geospatial integration tool for building a spatial entity matching benchmark[END_REF], is addressed to experts and it serves to build a characterized dataset in a semi-automatic process through the sets of three LBS providers namely Google Maps, Nokia Here Maps and Geonames. Let E 1 , E 2 and E 3 be the datasets of the three LBS providers respectively. Experts can search for a specific or random source entity from one provider, and then GeoBench searches for the nearby target entities from the two others separately. For each retrieved target entity, an expert has to decide whether it corresponds to the source entity and to select the differences that exist between the two entities at each level (spatial, primary and secondary terminological).

Concerning the secondary terminological level, only the most common secondary information is considered namely phone number, website and address. These three secondary attributes may have Missed Data (MD) or Syntactic Difference Data (SYN) assuming that it is impossible to have a Semantic Different Data (SEM) according to the information that they represent (e.g., two corresponding phone numbers may be syntactically different but can never be semantically different).

In this case, the number of the possible situations decreases from 96 to 48. In other contexts, the Semantic different Data (SEM) may be considered (e.g., when comparing the food type of two entities of restaurant's type, Pizza vs Italian food). GeoBench allows us to create a dataset E = E 1 ∪ E 2 ∪ E 3 in which, for each pair of entities, we know the relevance of correspondence and the situation of differences. Note that E 1 , E 2 and E 3 contain only the entities processed by GeoBench and not the whole set of entities of the three LBS providers.

The second module has been implemented to generate the test cases, it uses the dataset E created by GeoBench to generate source and target datasets for each situation s ∈ Situations dif . This module allows to configure the characteristics of a test case through a set of parameters in order to control aspects such as situation of differences, percentage of correspondences and percentage of noise. Once the characteristics of a test case are configured, source and target datasets are generated with a ground truth file so the evaluators can assess the results of their approaches. The module will search for all pairs of entities that match the requested situation of differences, then the entities of each pair will be distributed between the source and the target datasets and, the identifiers of corresponding entities will be listed together in the ground truth file. Finally, noise entities will be added to the target dataset or source dataset. IV represent the number of entities of each provider's dataset and the number of correspondences between them. Table V provides the top five test cases according to the number of detected correspondences. More statistics are available online along with PABench [START_REF]PABench[END_REF]. Retrieved datasets describe real world POIs where entities have been retrieved from several existing LBS providers using their web services. These datasets do not contain any redundancies or duplicated entities. The current version of the benchmark, as of October 2014, contains 1070 corresponding entities. All entities are available in CSV/SQL standard format to be easily parsed and used. To ensure that the test cases are rich enough, entities are distributed in several geographical zones/countries and refer to POIs of several types including large POIs and small POIs. Note that in the practice of the LBS context, some situations of differences rarely occur (e.g., the situation where two entities from different providers have no difference at all).

Statistics shown in Table

In the future, we intend to develop an entity generator tool that takes a subset of source entities to modify the values of their attributes (spatial, primary and secondary terminological) in order to create a target dataset that expresses these rare situations.

VI. ANALYZE AND FIRST USE OF PROVIDERS' DATASETS

In this section, we demonstrate the resistance of the benchmark against frequently used basic measures. To reach this goal, a simple matching tool (one similarity measure and a threshold) is used to determine the difficulty of the spatial entity matching task and to show the heterogeneity of our collected dataset. Our basic matching tool consists in comparing the values of a single terminological attribute using a string similarity measure. Entity pairs that have the highest similarity score above a given threshold are considered as corresponding. This simple approach is used to match E 1 with E 2 and E 1 with E 3 . Concerning the terminological information, we will compare the values of the NAME attribute using Levenshtein string similarity measure [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions and reversals[END_REF]. Experiments are repeated by varying the threshold value. The results are measured in terms of precision, recall and F-measure (see Section IV-C). Figures 2(a) and 2(b) show the matching quality of E 1 with E 2 and E 1 with E 3 respectively. The x-axis represents the values of threshold and the y-axis represents the values of precision, recall and F-measure. For a small value of threshold (0.1), the precision is low (75% for E 1 vs E 2 and 85% for E 1 vs E 3 ), which means that 25%-15% of detected corresponding entities are not correct according to the ground truth. However, the recall is high (99% in both cases), which means that the matching approach does not miss any of the ground truth correspondences. Increasing the threshold increases the precision and decreases the recall. For a high value of threshold (0.9), precision increases up to 98% in both cases, which indicates that most of the detected correspondences are correct according to the ground truth.

Conversely, the recall decreases to approximately 50%, which means that the half of the ground truth correspondences are missing. A trade-off is reached for a 0.5 threshold, in which case the F-measure is up to 80% for E 1 vs E 2 and 90% for E 1 vs E 3 , which indicates that using a simple matching method is not enough to resolve the matching problem. Similar results are obtained when the Levenshtein measure is replaced by the JaroWinkler measure [START_REF] Jaro | Advances in record-linkage methodology as applied to matching the 1985 census of tampa, florida[END_REF][39] [START_REF] Jaro | Probabilistic linkage of large public health data files[END_REF] (see Figures 3(a) and 3(b)).

A trade off is achieved with a 0.8 threshold and the F-measure is up to 80% for E 1 vs E 2 and 87% for E 1 vs E 3 . Except that JaroWinkler keeps the same quality with threshold up to 0.6 while it decreases with Levenshtein from 0.4, this means that the scores calculated by Levenshtein for corresponding entities is lower than the scores calculated by JaroWinkler. The two similarity measures are approximately equivalent in terms of results' quality, but the Levenshtein metric is more efficient in terms of execution time. Table VI compares their execution times according to the number of entities in matched datasets.

These experiments show that basic similarity measures are not enough to match the real and heterogeneous data of PABench. Note that matching E 2 with E 3 have the same trend as matching E 1 with E 2 and E 1 with E 3 . VII. CONCLUSION Spatial entity matching has become a basic problem in many application domains such as heterogeneous locationbased services. In this paper, we highlighted the absence of a benchmark to compare and evaluate spatial entity matching approaches. We proposed a taxonomy that characterizes differences, heterogeneities and errors between LBS providers at four levels: schema, terminology, spatial and availability. We studied the impact of the identified differences on the results' quality of a matching approach and we proposed the necessary specifications to design a benchmark, called PABench, that serves to evaluate and compare spatial entity matching approaches. We believe that our proposition will allow researchers to better evaluate their matching approaches, identify the capabilities of their approaches, and also guide performance improvements in existing spatial entity matching approaches. In the future, PABench may be extended by 1) adding more entities and 2) automatically generating entities to cover the situations of differences that occur only rarely in the LBS context. Also, we intend to create a survey that compares and evaluates existing approaches in terms of results' quality and execution time using our benchmark. This evaluation will explain the weaknesses and the strengths of current works, which will help to propose a better matching approach. On the other hand, the proposed taxonomy is limited to punctual geographical objects, but it may be extended to cover complex objects (e.g., polygons and lines) in order to be used for complex geographical data.

∃

  att ∈ B , ∃ att ∈ B \ (p = p ) ∧ (p .type = p .type) ∧ (f (e ) = p ) ∧ (f (e ) = p ) ∧ ((e .NAME.val ∼ = e .NAME.val) ∨ (e .att .val ∼ = e .att .val))

Figure 1 .

 1 Figure 1. Example of the Equipollent Positions difference: Two corresponding entities refer to the IUT Lyon 1 University (large POI) having different locations but both are correct.

  (p = p ) ∧ (p .type = p .type) ∧ (f (e ) = p ) ∧ (f (e ) = p ) ∧ (e .LATITUDE.val = e .LATITUDE.val) ∧ (e .LONGITUDE.val = e .LONGITUDE.val) 4) Entity's Availability:

Figure 2 .Figure 3 .

 23 Figure 2. Results' quality in terms of precision, recall and F-measure using Levenshtein similarity measure.

Definition 3 :

 3 Entity of POI An entity of a POI of a provider k, denoted by e ∈ E k , is an instance of the schema S k and refers to one real-world POI p ∈ P. e ={(id k .label, id k .val) , (LATITUDE k .label, LATITUDE k .val) , (LONGITUDE

k .label, LONGITUDE k .val) , (NAME k .label, NAME k .val) , (TYPE k .label, TYPE k .val) , attB 1 k .label, attB 1 k .val , ..., (attB r k .label, attB r k .val)}

TABLE I .

 I EXAMPLE OF TWO ENTITIES x AND y, OFFERED BY TWO DIFFERENT PROVIDERS, THAT REPRESENT THE POI ET (Eiffel Tower) WITH TWO DIFFERENT SCHEMAS DisplayName in the schema of the provider 1 and the attribute name in the schema of the provider 2 represent the name of the POI but they have different labels. Consider two attributes att i 1 ∈ S 1 and att j 2 ∈ S 2 , S 1 and S 2 have an attribute heterogeneity difference iff

	Model	Entity x (offered by provider 1)	Entity y (offered by provider 2)
	I	EntityID : 51190385	id : fd0cfb424bbd79bf28a832e1764f1c2aa5927714
	L	Latitude : 48,858606	geometry : { location : { lat : 48.85837,
		Longitude : 2,293971	lng : 2.294481}}
	A	DisplayName : Tour Eiffel	name : Eiffel Tower
		EntityTypeID : 7999	types : establishment
	B	Phone : 0892701239	formatted phone number : +33 892 70 12 39
		CountryRegion : FRA	website : http://www.tour-eiffel.fr
		Locality : Paris	formatted address : Champ de Mars,
		PostalCode : 75007	5 Avenue Anatole France, 75007 Paris, France
		AddressLine : Champ De Mars, Avenue Anatole France ...	...

  Table I refer to Eiffel Tower, but they have different longitude and latitude values. The distance between the two locations is approximately 226 meters. This difference is classified as Inter-Difference. e 1 ≡ e 2 ∧ (e 1 .LATITUDE.val = e 2 .LATITUDE.val ∨ e 1 .LONGITUDE.val = e 2 .LONGITUDE.val) This difference appears when the corresponding entities refer to a large POI and have different locations, but those locations are both correct with regard to the location of the POI that they represent. That is, corresponding entities' positions are equivalent in terms of concept but not in terms of values. This difference is classified as Inter-Difference. (e 1 ≡ e 2 ) ∧ (e 1 .LONGITUDE, e 1 .LATITUDE) ⊂ p.coordinates ∧ (e 2 .LONGITUDE, e 2 .LATITUDE) ⊂ p.coordinates ∧ (e 1 .LONGITUDE.val = e 2 .LONGITUDE.val ∨ e 1 .LATITUDE.val = e 2 .LATITUDE.val) Figure 1 shows two corresponding entities refer to the IUT Lyon 1 University (large POI) and have different locations (center of gravity vs entrance gate) but both are correctly represented.

	Equipollent Positions (EP):

TABLE II .

 II CONTINGENCYTABLE OF EVALUATION MEASURES.

	a Matching a a a approach Corresponding entities a Ground truth a a a a a	Corresponding entities True Positive (TP)	Non-corresponding entities False Positive (FP)
	Non-corresponding entities	False Negative(FN)	True Negative (TN)

TABLE III .

 III TAXONOMY OF DIFFERENCES AND QUALITY MEASURES IMPACT.

	Category	Difference	Intra-Diff	Inter-Diff	Impact
	Schema	Attribute Heterogeneity	X(dynamic schema)	X
		Different structure	X(dynamic schema)	X
	Terminology	Different Data (SEM)		X	TP	FN
		Different Data (SYN)		X	TP	FN
		Missing Data (MD)		X	TP	FN
		Similar Data (SD)	X	X	FP
	Spatial	Different locations (DL)		X	TP	FN
		Equipollent Positions (EP)		X	TP	FN
		Superposition (SUP)	X	X	FP
	Availability	Not found POI		X	FP
		Duplicate Entities	X		TP (wrong value)

TABLE IV .

 IV NUMBER OF ENTITIES AND CORRESPONDENCES PRODUCED USING GEOBENCH (OCTOBER 2014).

	Dataset	Number of entities	Number of correspondences
	E1	715	E1 , E2	569
	E2	583	E1 , E3	254
	E3	282	E2 , E3	247
	Total	1580	Total	1070

TABLE V .

 V TOP FIVE TEST CASES ACCORDING TO THE NUMBER OF DETECTED CORRESPONDENCES (OCTOBER 2014).

	Test Case #	Situation	Number of Correspondences
	43	{EP, SYN, {SYN, MD}}	145
	27	{DL, SYN, {SYN, MD}}	78
	41	{EP, SYN, SYN}	69
	35	{EP, SEM, {SYN, MD}}	62
	11	{0, SYN, {SYN, MD}}	60

TABLE VI .

 VI EXECUTION TIME FOR LEVENSHTEIN AND JAROWINKLER ACCORDING TO THE NUMBER OF ENTITIES IN MATCHED DATASETS.

	Datasets	Number of comparisons	Execution time of Levenshtein (sec)	Execution time of JaroWinkler (sec)
	E1 vs E2	715 × 583	11	840
	E1 vs E3	715 × 282	5	400
	E2 vs E3	583 × 282	4	320

ACKNOWLEDGMENT

This work was supported by the LABEX IMU (ANR-10-LABX-0088) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). Authors would like to thank Google Maps, Geonames, Open Street Map and Nokia Here Maps for providing POIs' entities.


Betsy R Seiffert
email: betsy.seiffert@ec-nantes.fr

G Ducrozet

Deep water wave-breaking in

published or not. The documents may come

Introduction

In nature, a steep wave may grow to surpass some limiting threshold leading to a collapse of the water surface as a broken wave. Energy from the wave is transferred through the generation of currents and turbulence, and changes occur in the spectral distribution of energy before and after a wave breaks.

The numerical models used in this study, HOS-ocean and HOS-NWT, are computationally efficient, open source codes that solve for highly nonlinear wave fields in the open ocean and a numerical wave tank, respectively, using the High-Order Spectral (HOS) method (Ducrozet et al. [START_REF] Ducrozet | 3-D HOS simulations of extreme waves in open seas[END_REF], Bonnefoy et al. [START_REF] Bonnefoy | Advances in Numerical Simulation of Nonlinear Water Waves[END_REF], Ducrozet et al. [START_REF] Ducrozet | A modified High-Order Spectral method for wavemaker modeling in a numerical wave tank[END_REF]). Due to the assumptions of solving for potential flow, the HOS solvers assume a single-valued free surface and therefore cannot produce breaking waves. The goal of implementing a wave-breaking mechanism into the HOS models is to approximate the broken free surface as a single value. By determining some means of accounting for wave-breaking within the HOS models, we can increase the application range of the models including calculating more extreme sea states. An accurate description of the wave field is necessary for predicting dynamics of offshore vessels and marine renewable energy devices, predicting loads on marine structures and the general physics of ocean waves, for example.

To implement a wave-breaking mechanism into the HOS models, first a wave-breaking onset parameter that can be calculated within the models needs to be identified, and second, a strategy for dissipating and distributing the energy after the wave has broken needs to be determined.

Wave breaking onset

The nonlinear and irregular processes that occur just before a wave breaks make predicting the onset difficult. Wave-breaking onset criteria is traditionally classified into one of three categories: geometric, kinematic or dynamic. Perlin et al. [START_REF] Perlin | Breaking Waves in Deep and Intermediate Waters[END_REF] provides a recent review of each of the three wave breaking criteria and the strengths and limitations of each.

In their numerical calculations, Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF] proposed a wave breaking threshold parameter based on the ratio of local energy flux velocity to the local crest velocity. The local energy flux velocity is calculated as the ratio of the local energy flux vector to local energy density. Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF] defines this breaking criterion as B x = F x /EC x where F x and C x are the projections in the direction of wave propagation (in this case, the x-axis) of energy flux and crest velocity, respectively, and E is the local energy density. Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF] determined wave breaking occurs in the narrow range of 0.85 < B x < 0.86. Saket et al. [START_REF] Saket | Wave breaking onset of two -dimensional deep -water wave groups in the presence and absence of wind[END_REF] investigated the breaking criterion of Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF] experimentally and found B x to be 0.84 ± 0.016, which is in good agreement with Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF]. Additionally, Saket et al. [START_REF] Saket | Wave breaking onset of two -dimensional deep -water wave groups in the presence and absence of wind[END_REF] found this threshold parameter to be robust for different classes of wave groups and wave steepness.

It is noted at the free surface, the energy flux velocity reduces to the water particle velocity, reducing this dynamic breaking criterion to a kinematic criterion. This is different from the traditional kinematic breaking criterion which states U/C ≥ 1, which would under predict wave-breaking events according to Perlin et al. [START_REF] Perlin | Breaking Waves in Deep and Intermediate Waters[END_REF], Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF], and Saket et al. [START_REF] Saket | Wave breaking onset of two -dimensional deep -water wave groups in the presence and absence of wind[END_REF], for example. It is advantageous to use the breaking criterion of Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF] as is straightforward to calculate in the HOS solver, applicable to 2D and 3D, and has a narrow threshold. However, since the wave is not of permanent form, the calculation of the wave crest velocity is non-trivial and must be calculated carefully.

Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF] measured a forward and backward leaning cycle of a wave crest as it moves through a wave train, and it is at the point close to when the crest is moving at its slowest speed that the wave breaks. Therefore a method of calculating the crest velocity that can accurately capture this slow-down is essential to accurately predict breaking onset.

Calculating wave-breaking onset in the HOS model

To calculate wave breaking onset in the HOS solvers, the criterion described by Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF] is tested. In 2D, the breaking criterion reduces to the ratio of water particle velocity to crest velocity in the direction of wave propagation, which can be written in terms of velocity potential as follows:

B x = F x /E C x = U x C x = ∂φ ∂x 1 C x < threshold (1)
As mentioned above, the calculation of wave crest velocity is non-trivial and must be able to capture the crest slow-down that occurs just before the wave breaks. A method of calculating the instantaneous crest velocity C x (x, t) using the partial Hilbert transform is used to overcome this problem. Following Kurnia and van Groesen [START_REF] Kurnia | High order Hamiltonian water wave models with wave-breaking mechanism[END_REF], the instantaneous, or local crest speed and local wave number are defined by

C x (x, t) = g • tanh(k(x, t) • h) k(x, t) , k(x, t) = 1 η 2 + H 2 [η] η ∂ ∂x H[η] -H[η] ∂ ∂x η (2)
and H[η(x, t)] is the partial Hilbert transform with respect to x.

Figure 1 shows a "chirped" wave packet, generated using the HOS-NWT solver following the method outlined in Song and Banner [START_REF] Song | On Determining the Onset and Strength of Breaking for Deep Water Waves. Part I: Unforced Irrotational Wave Groups[END_REF], which is a widely used method of generated controlled breaking waves in the laboratory. The two columns on the left show the surface elevation and free surface modal amplitude for a wave with a maximum breaking parameter B x = 0.79825 at time t = 24.85 s, which would be classified as an "unbroken" wave following Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF] and Saket et al. [START_REF] Saket | Wave breaking onset of two -dimensional deep -water wave groups in the presence and absence of wind[END_REF]. The two columns on the right show the surface elevation and free surface modal amplitude of a slightly larger wave packet where the breaking parameter is calculated as B x = 0.85091 at the time t = 28.50 s, which would be just above the threshold of Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF] and Saket et al. [START_REF] Saket | Wave breaking onset of two -dimensional deep -water wave groups in the presence and absence of wind[END_REF] to be classified as a "broken" wave. At t = 10.00 s, 24.85 s and 28.50 s, the surface elevation and modal amplitudes are comparable between the "unbroken" and the "broken" wave. However, at t = 38.39 s, the "unbroken" wave returns to its original amplitude and modal distribution, whereas the "broken" wave shows some high frequency components "Unbroken"

Figure 1: Free surface and free surface modal amplitude for an "unbroken" and "broken" wave at t =10.00 s, 26.75 s, 28.50 s and 38.39 s. The "unbroken" wave reaches a maximum B x = 0.79825 at time t = 26.75 s before returning to its original amplitude and modal distribution. The "broken" wave reaches a maximum of B x = 0.85091 at the time t = 28.50 s then shows high-frequency components in the free surface and in its modal distribution at t = 38.39 s.

in the free surface and in its modal distribution. This is likely an artifact of a wave which in nature would overturn, but since the HOS model solves for a single-valued free surface, these high frequencies develop instead. This suggests that a threshold of B x ≈ 0.84-0.86 as suggested by Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF] and Saket et al. [START_REF] Saket | Wave breaking onset of two -dimensional deep -water wave groups in the presence and absence of wind[END_REF] would distinguish between a broken and an unbroken wave in the HOS solvers.

A comparison is made between the experimental measurements of Saket et al. [START_REF] Saket | Wave breaking onset of two -dimensional deep -water wave groups in the presence and absence of wind[END_REF] and those calculated using HOS-NWT for local wave steepness (S c ) as defined in [START_REF] Saket | Wave breaking onset of two -dimensional deep -water wave groups in the presence and absence of wind[END_REF], and breaking parameter (B x ) for maximally recurring and marginally breaking waves in Table 1. In these experiments, breaking waves were generated using "chirped" wave packets, as in Fig. 1. In the HOS-NWT calculations, B x is calculated at at each location x and time step. If the calculated B x surpasses the threshold of 0.84, then the wave is classified as "broken", the simulation is stopped, and the calculated B x and S c are reported at this time. If B x did not surpass 0.84, then the maximum B x and corresponding S c are reported and the wave is classified as "unbroken". Although HOS-NWT calculates slightly larger wave steepness when breaking than Saket et al. [START_REF] Saket | Wave breaking onset of two -dimensional deep -water wave groups in the presence and absence of wind[END_REF], the results are still in reasonable agreement.

The numerical calculations of Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF] also used chirped wave packets to produce breaking waves. Results for calculated wave breaking parameter and corresponding local wave steepness are shown in Fig. 2 for the numerical calculations of Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF] and Saket et al. [START_REF] Saket | Wave breaking onset of two -dimensional deep -water wave groups in the presence and absence of wind[END_REF] along with a set of calculations using chirped wave packets in HOS-NWT, as well as modulated and random waves, calculated using HOS-ocean. Classification of "broken" and "unbroken" waves are the same as those above with a threshold of 0.84. The hollow markers represent unbroken waves and the solid markers are broken waves. The breaking parameters and corresponding local wave steepness calculated using HOS-NWT and HOS-ocean are in good agreement with the Barthelemy et al. [START_REF] Barthelemy | On the local properties of highly nonlinear unsteady gravity water waves[END_REF] calculations and Saket et al. [START_REF] Saket | Wave breaking onset of two -dimensional deep -water wave groups in the presence and absence of wind[END_REF] experiments, giving us confidence in the applicability of this breaking parameter in the HOS models.

Conclusion

Due to the assumptions of calculating for potential flow, the HOS solvers require a single-valued free surface and therefore cannot calculate breaking waves. The goal of this study is to be able to approximate a broken free surface as a single value. To do this, we need to determine a measurable wave breaking onset criteria, and determine a strategy for wave energy dissipation and distribution after the wave has broken. So far, we have identified a robust wave breaking onset criteria which has been successful in identifying the threshold at which a wave is "broken" in the HOS solvers, evidenced by the manifestation of high frequency components in the surface elevation and modal distribution in a "broken" wave. Further research is needed to determine the wave energy dissipation and distribution. Wave steepness S c and breaking parameter B x measured for maximum recurring and marginally breaking waves measured in the experiments of Saket et al. [START_REF] Saket | Wave breaking onset of two -dimensional deep -water wave groups in the presence and absence of wind[END_REF] and calculated using using HOS-NWT.

Table 1 :

 1 Breaking parameter B x versus crest steepness S c . Hollow points represent unbroken waves and solid points represent broken waves. The zone 0.84 < B x < 0.86 is the breaking and S c > 0.72 is the deep water Stokes limit.

	Barthelemy Calculations
	Saket Experiments
	HOS Chirp
	HOS Saket
	HOS Modulated
	HOS Random
	Figure 2:


Keywords: analyse lexicale, analyse syntaxique, Lex, Prolog, DCG, Definite Clause Grammar

Programmer des analyseurs syntaxiques efficaces en

Prolog: le manuel CLF (v1.0)

Résumé : Ce document décrits deux outils utiles pour rapidement concevoir et développer des langages informatiques. Le premier utilise Flex pour constuire des analyseur lexicaux, le second est une extension des DCG de Prolog pour construire des analyseurs syntaxiques. À l'origine conçu comme un nouveau composant du système Centaur, ces outils sont maintenant disponibles de façon indépendante. Les analyseurs produits peuvent être intégrés dans des systèmes écrits en Prolog ou dans d'autres langages. Ceci est la verion initiale du document, des versions mises à jour seront disponible en ligne si nécessaire

Introduction

The initial goal of the Computer Language Factory (CLF) was to enhance the trilogy of formalisms Metal/PPML/Typol used in Centaur [START_REF] Borras | Centaur: the system[END_REF] to prototype the syntax and the semantics of computer languages. The Centaur system was a syntactic editor, written in Lisp, and was able to call external modules as parsers or semantic tools that was specified using specific formalisms. However, with the premature end of the development of the Centaur sytem, this goal was not completely achieved.

The current version of CLF has been rebuild to permit a fast an easy developpement of efficient parsers in Prolog, combining Flex and an extended version of Prolog DCGs [START_REF] Clocksin | Programming in Prolog[END_REF][START_REF] O'keefe | The craft of Prolog[END_REF][START_REF] Blackburn | of Texts in Computing[END_REF].

RT n 0328

It has been used in the AxIS1 team to produce a parser for XML and some derived languages [START_REF] Despeyroux | Practical semantic analysis of web sites and documents[END_REF]. These parsers has been used intensively to parse a great number of Xhtml and XML files. As an exemple, parsing a 24 millions charaters (614000 lines) OWL ontology takes only 13 seconds on a 2 Mhz Pentium laptop with 1MB of memory, while loading of the same triples takes 50 seconds with Protege.

One can imagine and use a computer formalism without any concrete syntax. This can be the case for example for an intermediate code formalism that does not need to be visualized. In this case only an abstract syntax can be given. However most computer languages have a concrete syntax. In the case of a translator we can want to define only an unparser for the target language, but most of the time one will need also a parser and thus a scanner. The parser is thus a very important interface between the human and the computer representation of programs or any other formalized documents.

As it was the case for Metal [START_REF] Kahn | Metal: A formalism to specify formalisms[END_REF] in the Mentor [START_REF] Donzeau-Gouge | Programming environment based on structured editors: The mentor experience[END_REF] and Centaur [START_REF] Borras | Centaur: the system[END_REF] systems, the CLF does not use its own formalism to formalize a scanner, but uses an interface to scanners generated with Flex.

Unless the traditional use of Lex and Yacc, we consider the process of analysing some text as a translation from a list of tokens to a target language. With this approach the lexical analyser and the scanner are not linked together, so they can be developped and debbuged separatly. On multi processors or multi cores systems, the lexical analyser and the parser can be dispatched, improving performances for the user.

A great difference between the Centaur implementation and the current one is that we do not use any abstract syntax declaration. So there is no static analysis of the source code and the constructed term is a completely free Prolog term.

Rational

As a preamble, we think that it is easier and safer to specify than to directly program. This is in particular true when one want to modify an existing program: a specification is in general much simpler as it does not contains tedious programming details.

The global scheme used to construct scanners in the Computer Language Factory is inherited from Metal. We have chosen to use an efficient existing scanner generator (Flex) and to design a protocol to connect the generated scanners to the rest of the factory. This view is different from what is done with SDF [START_REF] Klint | A meta-environment for generating programming environments[END_REF] or Syn [START_REF] Boulton | Syn: A single language for specifying abstract syntax trees, lexical analysis, parsing and pretty-printing[END_REF] which incorporate specific sections to specify the lexical elements into the complete syntax definition.

This choice has been made not only because of the efficiency of Lex generators but also because it is very flexible.

Some other important reasons lead our choice. First, we would like that the generated scanners can be used in different manner, connect to Centaur (written in Lisp), directly to Prolog or any other system. Second, we would like to be able to run the scanner alone for debugging. This important feature was missing in the Metal implementation in which it is impossible to test a scanner independently from a parser. It is also missing when Lex is used in its traditional way, connected to Yacc or Bison. In our appraoch the scanner and the parser are not linked together and run as different process. A special mode allows an easy debugging of the scanner.

Unless it is done for Metal, we do not try to generate a skeleton that must be then modified by a Sed script. This part of building a scanner with the help of Metal was too tedious and generated also a lot of problems because it asked to write Sed scripts and not directly Lex specifications. The generation of a skeleton of this Sed scripts by Metal is also useless when one wants to modify an initial specification. Rather than mechanizing half of the job, we preferred as a first sketch to let the entire responsibility of specifying the scanner to the user. We allow the use of plain Lex specifications, modulo the use of a specialized library that implements the interface. The fix part of the proposed Flex skeleton is rather small, and due to the technology that is used by the parser, there is no need for special keywords corresponding to entry points of the parser as it is the case with Metal. So the user has really to specify only the atoms of its language, this have to be done anyway, and the keywords of its language. However, one can imagine to write a processor that will check that all tokens and keywords used in a concrete syntax definition is defined in the correspondent Lex definition.

There is no encoding of keywords as it was done in Metal. The raw strings of characters are used. Even if this will slow down a little the communication between the generated scanners with the rest of the system, this simplify a lot the process of building scanners and parsers, and in fact we think that data compression is the job of the protocol that is used, not the job of the user.

Concerning the parsing phase, the extensions we propose have several goals. The first ones deal with efficiency and expressiveness. The last ones deal with a real lack in traditional generated parsers when there are used in complex environment: the link between the source text and the rest of the system is in general done in an ad-hoc way. Here are the goals we want to reach: allow right recursion in grammar rules: right recursion may be natural when giving a grammar for a particular language, however it may lead to infinite loops during Prolog execution; by transforming right recursive rules into non recusive ones we improve the expressiveness of the formalism, make use of Prolog compiler optimisations: most of modern Prolog compiler or interpreteur use indexing on some arguments to improve clause selection. By transforming rules with similar beginning of their right part, we can take benefit of indexing for better performance, generate some code to retrive the location of parsing errors in the text that is analysed, generate some code to allow an easy correspondance between the constructed prolog term and the source code that is analysed. This correspondance will be used in RT n 0328 subsequent processors, for exemple compilers or translators to produce accurate error messages, provide a way to easily keep or discard comments.

Our extension of DCGs uses in fact the Prolog syntax and is translated by a preprocessor to pure DCGs. There is no static analysis as there is no abstract syntax declaration.

The current version version of the CLF has been used to generate a parser for XML, then to extend this parser to produce a rule language that manipulate XML expressions with logical variables. Its appears that it was simpler and safer to generate a new parser for XML, and then to modify this parser than to use an existing one.

Tutorial

Defining a scanner

Defining a scanner for the CLF is not very different from defining a scanner with Flex only. Only two constraints must be followed:

1. A skeleton that includes the interface must be used.

2.

A library must be used to "emit" the tokens that are identified.

The output of the scanner will distinguish the different tokens by their kinds. There are three basic kinds of tokens: keyword This kind contains the reserved words of the language that is analyzed and the punctuation.

itoken Integer tokens are all the tokens whose values are integers.

stoken String tokens are all the tokens whose values are strings, such as identifiers for example.

They may be several classes of integer or string tokens. We will see that they will be distinguished by a name.

Three more kinds of tokens are used for practical reasons:

nl To signal new lines, so it will be possible to count them and report a line number when needed.

comtext To identify the text of a comment, when comments must be kept fir use with a syntactical editors for example.

error To report an erroneous token that cannot be identified by the scanner.

The following sections explain how to construct the lex specification to build a scanner. They also give some basic and useful examples. More information on how to build a Flex scanner must be found in the Flex manual. This skeleton already imports (#include) two files (Tokens-flex-define.c and Tokensflex-proto.c) used by the Tokens environment. This environment defines some functions that must be used to return the tokens that has been identified.

The interface with the host system uses a fix part that must replace the line #include Tokens-flex-fixpart. As includes are not allowed in the body of a Flex definition, the job can be done by hand or with the help of a preprocessor.

The different sections are described in detail below.

Contexts

The following contexts must be present by default.

%S waitdata sentences comment comm incomm

If some more contexts are necessary to define the scanner of an object language, some new contexts can be added to this list.

The context "waitdata" is only used by the interface. It is use to indicate some options and modes to the scanner that is generated. The users should not use this context.

The context "sentences" is the context in which phrases of the object language must be scanned. Most of the job of the scanner will be done here.

The context "comment" is the context in which comments that are found in an object program text must be scanned. When the generated scanner identifies the beginning of a comment, it must switch to this context.

The contexts "comm" and "incomm" are used to analyze comments that are not embedded in a complete program (i.e. when one want to analyze only the text of a comment). These two contexts was only used by Centaur to edit comments.

Examples for the two mostly used forms of comments are given later on.

RT n 0328

Regular Expression Abbreviations

As in every Flex specification the user can define some abbreviations that will be used in the rest of the specification. One will refer to the Flex manual for more information.

The proposed treatments for C-like comments will define some regular expression abbreviations.

Fix Tokens Interface

The same scanner can be used in different ways: connected to the Centaur system, connected directly to Prolog to execute a Typol specification, or in a debug mode. It can also be used to analyze a complete file or only a given piece of text.

To achieve this, the context "waitdata" will recognize some keywords used by the host system to identify itself. It can also set some variables that will be used by the syntactic analyzer.

The line #include Tokens-flex-fixpart must be replaced by some fix Flex definitions. A ed script to perform this transformation can be found in the Tokens lib directory and is called by the suggested Buildfile. Be aware that due to this inclusion, error messages produced by Flex will be shifted (by 20 lines when done by the ed script).

As the generated scanner may be used in a server mode, the end-of-file character is not sufficient to mark the end of inputs. A cryptic keyword that we hope will never appear in programs is used (we can suspect some bootstapping problems here!). See details in the "Stans Alone Exection" section.

Comments Definition

This part may be omitted in a first attempt to define a lexical analyzer. However to analyse real programs it should be defined anyway.

Two very usual classes of comments are defined somewhere else in this document as examples. One can adapt them very easily.

These two examples are:

C-like Comments These comments can be found every where in the text. They start with some particular string ("/*" in C) and end with an other one ("*/" in C). They may spread over several lines.

ADA-like Comments

These comments start with some particular string (two "-" in ADA) somewhere on the line and end at the end of the line. They cannot spread over several lines.

In the current version of Tokens, comments are passed over to the Centaur system, while it is not the case when the scanner is connected directly to Prolog.

Tokens Definition

This is the real part of the scanner definition. It must contain the definition of the keywords (including punctuation and other signs) and the definition of all the tokens of the language (identifiers, numbers, strings, etc.). Tokens come in various classes, depending on the concrete syntax definition, that are identified by their names, for example ID for identifiers or UCID for identifiers starting with an uppercase letter.

INRIA

When a token as been identified, one of the function provided by the library must be used to return its value (the "return" action traditionally used in Flex must not be used directly): keyword(char* key) The string passed as argument must represent the keyword itself, no encoding is used as it was the case in Mentor or Centaur. The string must be the same that those that will be used in the parser definition.

itoken(char* tok, char *value), stoken(char* tok, char *value) The first function must be used to return tokens whose value is an integer, the second to return tokens whose value is a string.

The string tok is a token name. The same name must be used in the parser definition.

The string value is the value of the token. It is often useful to put this value in a canonical form, suppressing escape characters and boundaries. For example, the value of a string written ""aaa""bbb"" in the text of a program may be simply "aaa"bbb". Keeping this form in the abstract syntax tree will make easier the writing of the semantics of the language, in particular when one wants to write translations. Of course, the un-parser will have to take this into account, adding necessary quoting and escape characters. In the case of a non case-sensitive language, it will be also useful to normalize the identifiers, putting them in lowercase for example. Doing this, the semantics will not have to manipulate strings when comparing the equality of to strings.

New Lines

Every new lines must be reported. This will allow reporting of errors during parsing. This information is also used to make a correspondence between an occurence in the abstract syntax tree and the line number when one wants to execute and off-line version of the semantics.

At each new line, a call to the function nl() must be done. Be careful to report also new lines that occur inside some tokens (in particular comments), otherwize line numbers reported by the parser or by the semantics will be erroneous.

C User's Functions

As in every Flex definition, this part may contain C functions that are need by the scanner. They may be functions used to put some tokens in a canonical form, suppressing escape characters or boundaries for example. A catalogue of such functions for languages already used in Centaur is provided in the library.

Example

We will take as example the traditional Exp language, taken from the Centaur documentation.

This formalism uses some keywords (arithmetic signs), identifiers (let's say that they must start with uppercase letters, then continue with uppercase letters, digits or underscores) and integers. These tokens will be classified into 2 classes named ID and INT. ;

<sentences>--\n {comtext(""); nl();}; <sentences>"--" {BEGIN comment;};

RT n 0328

Defining a parser

Defining a parser in CS is very similar to using traditional DCGs. However, the sign --> is replaced by :-as in regular prolog clauses. Every DCGs documentation can thus be used.

Grammar rules

The following exemple shows an exemple of rules:

exp(plus(A,B)) :-exp(A), ['+'], exp(B). exp(minus(A,B)) :-exp(A), ['-'], exp(B).

As explain in the rational, right recursion is permited, as it is the case in this example. Moreover, the generated code will take advantage of the regularity of these rules to generate indexable clauses if necessary.

Unless traditional DCGs, all predicates must have an argument that explain how to construct the resulting term.

Notice that some production rules may only pass a term, not constructing a new one. This is in particular the case when production rules are used to manage prorities of syntactic operators for example:

exp(A) :-factor(A).
Lists are treated as ordinary prolog lists.

element_s([E|L]) :element(E), element_s(L). element_s([]).

Tokens

The special literal stoken must be used to connect the parser to the scanner. Its first argument must the name of the token as it is given in the scanner. The second argument is of the form string(A) or integer(A) depending on the type of the token.

Here is some examples.

exp(id(A)) :-stoken('IDENTIFIER',string(A)). exp(text(A)) :-stoken('TEXT',string(A)). exp(int(A)) :-stoken('INTEGER',integer(A)).

Theses rules correspond respectively to the following ones in the Lex definition:

stoken("IDENTIFIER",yytext) stoken("TEXT",yytext); itoken("INTEGER",yytext);

INRIA 4 User's Manual 4.

Producing a scanner

When a Flex specification for the CLF has been written, it must be compiled as any other Flex specification. The C code that is produced will be then compiled with a C compiler.

The scanner that is generated can be used independently for debugging, or used with a direct connection with Prolog.

Files Naming Convention

Suppose that we want to define a scanner for a formalism named Foo and that this scanner will be a component of a concrete syntax definition of Foo named std (remember that they may be several concrete syntax for a unique abstract syntax). The Flex definition of the scanner must be found in the file Foo-std-Tokens.lex and the generated scanner will be found in Foo-std-Tokens.

Compiling Flex Specifications

As usual, Flex specifications must be compiled by Flex, and the ouput produced by Flex compiled again by a C compiler.

The following example of Makefile will compile two scanners (named std and spc) for the language Foo. all: Foo-std-Tokens Foo-spc-Tokens include ..../clf//Tokens/BuildTokens The path .../clf/Tokens/lib must be set accordingly with the installation directory of CLF.

Be aware that due to the use of a preprocessor to include the fix part of the interface, error messages produced by Flex will be shifted (by 20 lines).

Stand Alone Execution

The generated scanners can be run in a stand alone mode for testing and debugging. Following our example, one can run the generated scanner typing ./Foo-std-Tokens, then the keyword [BEGINDATA] alone on one line. The scanner is ready to scan what arrives on its input and produces on its output one line for each token that is recognized, containing all information about the token (type, name, value). It will stop scanning when the string [)*&% !ENDDATA!%&*(] is entered alone on a line. It will restart scanning by typing [BEGINDATA] again.

It is also possible to scan a complete file by entering [PARSEFILE] immediately followed by the name of a file on a single line.

The exact protocol that is sent to Centaur or Prolog can be viewed by typing [TARGET]centaur or [TARGET]eclipse alone on one line before entering the command [BEGINDATA].

The scanner can be terminated typing the command [QUIT]. It is also possible to abort a scanner as every process.

Producing a parser

When a CS specification has been written, it must be compiled to Prolog DCGs.

The generated code can be used directly by a prolog program.

Files Naming Convention

Suppose that we want to define a scanner for a formalism named Foo, and that we want to define the standard parser for this formalism. The CS definition of the parser must be found in a file named Foo-std.csp. When compiled to DCGs a Prolog file named Foo-std.sp will be created.

Compiling a Specification

The following example of Makefile will compile a parser define in Foo-std.csp.

all: Foo-std.sp expand_cs = .../clf/Syntax/expand_cs Foo-std.sp : Foo-std.csp ${expand_cs} Foo-std.csp Foo-std.sp

The path .../clf/Tokens/lib must be set accordingly with the installation directory of CLF.

Using a parser

To use a parser, one must define the following predicate in which "Foo" is the name of the formalism, "std" the name of the parser, and entry the name of the top production rule to be used.

'Foo-std-parser'(_A, __A) --> skip_comm(0, _1), entry(_A, __A, _1, _2), skip_comm(_2, _).

INRIA

The call to the parser itself will be defined as follow. The input of the predicate is the name of the file to be parsed. They are two results, a tree which is the abstract tree, and a special one used to make a correspondnance between occurences in the parsed tree and line numbers in the source. The first argument of the predicate clf parse is an absolute path to the lexical analysor produced by Flex. The second one is the name of the predicate to be caller, defined before.

Several files must be loaded (compiled) into prolog to get a complete parser.

:-compile("/home/.../clf/Parser/lex_caller.sp"). :-compile("/home/.../clf/Parser/clf_parser.sp"). :-compile("/home/.../clf/Parser/skip_comm.sp").

:-compile("/home/.../Foo/syntax/Foo-std.sp"). :-compile("/home/.../Foo/syntax/Foo-std-parser.sp").

The different paths must be set accordingly to the installation.

Reference Manual

The generation of lexical analyzers relies on a C library used by Flex that are detailed in the two following sections. They will be founded in the directory .../Tokens/lib.

Tokens Basic Library

The file Tokens-flex-proto.c contains the functions that must be used to return tokens from the generated scanner. Note that when Flex recognizes a token, its text value is kept in a string variable named yytext.

nl() Indicates that a new line must be taken into account.

comtext(char *a) Report the value of a comment. Don't forget that if you decide that boundaries are not part of the value, they must be added by the un-parser.

RT n 0328 stoken(char* tok, char *value) Report the value of a token implemented as string. The first argument is a string containing the class name of the token, the second one its value. To make easier the writing of semantics tools it is recommended that the values of tokens do not contain boundaries, neither escape character. In this case these must be properly added by the un-parser to generate back a correct text.

itoken(char* tok, char *value) Report the value of a token implemented as integer. The first argument is a string containing the class name of the token, the second one its value.

keyword(char *key) Report a token of class keyword. The argument is a string representing the keyword itself.

error(char *val) Report an erroneous token.

Functions on Strings

The file Tokens-flex-proto.c also defines some functions that can be used to manipulate strings before returning them. They modify directly the value of the variable yytext that Flex uses to keep the value of the tokens that have been recognized.

shiftleft() Suppress the first character from yytext. The last argument of the predicate clf parse returns a term that permit to make the correspondance between the parsed term and the source code. The structure reflects exactly the structure of the parsed term, but there is only one operator (node) that has one more son that contains a line number. For example, if the source text, stating at line 12 is

A + B

the construted term will be plus(id('A'),id('B'))

and the reference term will be node(12,node(12,nil),node(13,nil))

Implementation Notes

The goal of this section is to give an idea of the transformations that are performed on CS rules to produce standard DCG rules. We focus on two transformations that are used to take advantage of clauses indexing and to allow left recursion. Of courses these two transformationsshould be combined in some cases. We also focus only on the basic transformations, not taking into account additionnal parameters that are generated for other reasons.

When rules can be chosen by use of a discriminent token as in RT n 0328

INRIA

3. 1 . 1

 11 The Basic SkeletonAll Flex specifications used to generate a scanner for the Computer Language Factory must follow the following skeleton. %{ #include "Tokens-flex-define.c" %} %S waitdata sentences comment comm incomm <regexp abbreviations> %% #include Tokens-flex-fixpart <comments definition> <tokens definition> %% #include "Tokens-flex-proto.c" <C user's functions>

  RT n 0328 <sentences>[0-9][0-9]* itoken("INT",yytext); %% #include "Tokens-flex-proto.c"3.1.3 C-like CommentsC-like comments starts with the two characters "/*" and end with "*/". The following definition considers each line as one token. New-lines are not considered as part of the token. In this version, leading spaces at the beginning of the commens are removed. C1 [^*\n] C2 [^*/\n] Ca ({C1}*("*"*{C2})?)* Cb ({C1}*("*"*{C2})?)*"*"* <comment>{Ca}\n | <comment>{Cb}\n {suplast(); rmtabs(); comtext(yytext); nl();}; <comment>{Cb}"/" {BEGIN sentences; suplast2(); rmtabs(); \ comtext(yytext);}; <sentences>"/*" {BEGIN comment; }; <comm>.* {rm_leading_spaces(); comtext(yytext);}; <comm>\n nl();3.1.4 ADA-like CommentsADA-like comments start with two minus signs anywhere on the line and stop at the end of the line. In the following definition, the value of a comment does not include the two minus signs, neither the last new-line character.

  readfile(File,Tree,Refs) :-clf_parse(''/home/users/../Foo-std-Tokens'', 'Foo-std-parser', File, Tree, Refs).

shiftleft2( ) INRIA 5 . 3

 )53 Suppress the two first characters from yytext. suplast() Suppress the last character from yytext. suplast2() Suppress the two last characters from yytext. rmtabs() Replace tabs by spaces in yytext. rm leading spaces() Suppress spaces at the beginning of yytext. clear string(char c) Suppress any forcing character c from yytext. clear string1() Define the first character as beeing a forcing character, then suppress the first and the last characters and also any occurence of the forcing character from yytext. For example tranform the string 'foo''bar' into foo'bar. Example of use to define prolog-like atoms: <sentences>'([^'\n]*|'')*' {clear_string1();stoken("ATOM",yytext);}; clear string2() Suppress the first and the last characters and also any occurance of the forcing character backslash in yytext. Retrieving line numbers in the source

  a(X) :-['t1'], b(X). a(X) :-['t2'], b(X). ...the following code is produced a(X) -> [T], a$h(T,X). a$h('t1',X) -> b(X). ...We have chosen to perform the transformation only when 3 different tokens are used. When the following schema is used add(plus(A,B)) :-add(A), ['+'], mult(B). add(X) :-mult(X).

http://www.inria.fr/recherche/equipes/axis.en.html INRIA

RT n 0328

Thierry Despeyroux

the following code is produced

CS definition uses one parameter (the constructed term). The generated DCGs rules contain 4 ou 5 parameters. When extended again to prolog clauses this gives 6 or 7 parameters for each clause.

Thierry Despeyroux

The two regular expressions that recognize our tokens are:

Identifiers will be represented as strings in the abstract tree, while integers will be represented as integers. Thus there will be reported using respectively the functions stoken and itoken.

Comments are ADA-like comments starting with the % sign. They end at the end of the line Placing these elements in the skeleton give us the following definition: