Parsing structured data

• US 20040098668A1
• Filed: 08/20/2003
• Published: 05/20/2004
• Est. Priority Date: 03/23/2001
• Status: Active Grant

• Current Assignee: Nokia Corporation
• Original Assignee: Nokia Corporation
• Inventors: Vehkomaki, Tuomo
• Granted Patent: US 7,263,691 B2
• Time in Patent Office: Days
• US Class Current: 715/234
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149

Abstract

A method for parsing structured data has the steps of: receiving input data in a first computer language; generating a plurality of tokens according to the input data; building a context by using a grammar syntax comprising a set of rules, the context comprising a plurality of context steps in the form of at least one or more chains of context steps, the step of building the context comprising the sub-steps of: detecting if according to the grammar syntax a token is allowable in the context; and if the token is allowable, creating a new context step corresponding to the token, and the further steps for recovering an unallowable token: identifying a suitable context for the unallowable token in which context the token is allowable; and applying the token in the identified suitable context.

Claims

1. A method for parsing structured data comprising the steps of:

receiving input data in a first computer language;

generating a plurality of tokens according to the input data;

building a context by using a grammar syntax comprising a set of rules, the context comprising a plurality of context steps in the form of at least one or more chains of context steps, the step of building the context comprising the sub-steps of;

detecting if according to the grammar syntax a token is allowable in the context; and

if the token is allowable, creating a new context step corresponding to the token;

characterised in that the method comprises the further steps for recovering an unallowable token;

identifying a suitable context for the unallowable token in which context the token is allowable; and

applying the token in the identified suitable context.

2. A method according to claim 1, wherein the identifying of the suitable context comprises searching for a least different allowable context for the token using the grammar syntax.

3. A method according to claim 2, wherein the applying the token comprises modifying the context to be equal to the least different allowable context.

4. A method according to claim 2, wherein the searching for the least different allowable context attempts to generate a new context step according to a rule specific to the unallowable token to complement the context so that the unallowable token becomes allowable.

5. A method according to any of the preceding claims, wherein the method first attempts to complement the context by adding such a context step, which is allowable, according to the syntax, both to the preceding context step and to the unallowable context step.

6. A method according to claim 5, wherein, if such complementing fails, a backwards proceeding searching for the suitable context is performed.

7. A method according to any of the preceding claims, wherein at least one of a rule specific for the generic syntax of the first computer language and a type of token is used for determining whether a token is allowable in a context.

8. A method according to any of the preceding claims, wherein the method comprises a further step of dynamically switching to use another grammar syntax to adapt to a different language or to a different dialect of the language.

9. A parser comprising:

an input for receiving input data in a first computer language;

a tokeniser for generating a plurality of tokens according to the input data;

a context builder for building a context by using a grammar syntax comprising a set of rules, the context comprising a plurality of context steps in the form of at least one chain of context steps, the context builder being configured to;

detect if according to the grammar syntax a token is allowable in the context; and

if the token is allowable, to create a new context step corresponding to the token;

characterised in that

the parser further comprises for recovering an unallowable token;

an identifying block for identifying for the unallowable token a suitable context in which the token is allowable; and

the tokeniser is configured to apply the token in the identified suitable context.

10. A computer program product for controlling a parser comprising:

parser executable computer program code to enable the parser to receive input data in a first computer language;

parser executable computer program code to enable the parser to generate a plurality of tokens according to the input data;

parser executable computer program code to enable the parser to build a context by using a grammar syntax comprising a set of rules, the context comprising a plurality of context steps in the form of at least one chain of context steps, the code being configured to;

detect if according to the grammar syntax a token is allowable in the context; and

if the token is allowable, to create a new context step corresponding to the token;

characterised in that the computer program product further comprises for recovering an unallowable token;

parser executable computer program code to enable the parser to identify for the unallowable token a suitable context in which the token is allowable; and

parser executable computer program code to enable the parser to apply the token in the identified suitable context.

11. A processing unit having a parser comprising:

an input for receiving input data in a first computer language;

a processor for generating a plurality of tokens according to the input data;

a context builder for building a context by using a grammar syntax comprising a set of rules, the context comprising a plurality of context steps in the form of at least one chain of context steps, configured to;

detect if according to the grammar syntax a token is allowable in the context; and

if the token is allowable, to create a new context step corresponding to the token;

characterised in that the parser further comprises for recovering an unallowable token;

identifying block for identifying for the unallowable token a suitable context in which the token is allowable; and

the processor is configured to apply the token in the identified suitable context.

12. A processing unit according to claim 11, comprising a device selected from a group consisting of:

a translator, a gateway, a mobile station and a web server.

13. A system comprising a mobile telecommunications network and a gateway having a parser that comprises:

an input for receiving input data in a first computer language;

a processor for generating a plurality of tokens according to the input data;

a context builder for building a context by using a grammar syntax comprising a set of rules, the context comprising a plurality of context steps in the form of at least one chain of context steps, configured to;

detect if according to the grammar syntax a token is allowable in the context; and

if the token is allowable, to create a new context step corresponding to the token;

characterised in that the parser further comprises for recovering an unallowable token;

an identifying block for identifying for the unallowable token a suitable context in which the token is allowable; and

the processor is configured to apply the token in the identified suitable context.