Automated evaluation of grammars

• US 9,304,747 B1
• Filed: 12/12/2014
• Issued: 04/05/2016
• Est. Priority Date: 12/12/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Mielenhausen, Bjoern, Zengerle, Felix
• Primary Examiner(s): Deng, Anna
• Application Number:
  US14/569,445
• Time in Patent Office: 480 Days
• Field of Search: 717/143
• US Class Current: 1/1
• CPC Class Codes: G06F 8/31 Programming languages or programming paradigms
• CPC Class Codes: G06F 8/42 Syntactic analysis

Abstract

A method for automating evaluation of grammars associated with one or more programming languages is disclosed. The computer system accesses first grammar data associated with a first grammar and second grammar data associated with a second grammar, wherein a grammar comprises one or more rules that define a programming language. The computer system determines from the first grammar data and the second grammar data whether the first grammar and the second grammar correspond to the same programming language. Determining further includes applying one or more transformational steps to both the first grammar data and the second grammar data. After each transformational step, the computer system determines whether the first and second grammar data correspond. In accordance with a determination that the first grammar data and the second grammar data correspond, the computer system determines that the first and second grammar both correspond to the same programming language.

Claims

1. A method comprising:

accessing first grammar data associated with a first grammar and second grammar data associated with a second grammar, wherein a grammar comprises one or more rules that define a programming language that corresponds to the grammar;

determining from the first grammar data and the second grammar data whether the first grammar and the second grammar correspond to the same programming language, wherein determining whether the first grammar and the second grammar correspond to the same programming language includes;

applying one or more transformational steps to both the first grammar data and the second grammar data;

after each transformational step, determining whether the first grammar data and the second grammar data correspond;

in accordance with a determination that the first grammar data and the second grammar data correspond, determining that the first grammar and the second grammar both correspond to the same programming language; and

in accordance with a determination that the first grammar data and the second grammar data do not correspond, selecting a next transformational step in the one or more transformational steps, wherein prior to selecting the next transformational step;

determining whether there are any remaining transformational steps, and

in accordance with a determination that there are no remaining transformational steps, determining that the first grammar and the second grammar do not correspond to the same programming language.

2. The method of claim 1, wherein determining whether the first grammar and the second grammar correspond comprises determining whether the first grammar is an exact text correspond for the second grammar.

3. The method of claim 1, wherein the one or more transformational steps includes removing all actions from the first grammar data and the second grammar data.

4. The method of claim 1, wherein the one or more transformational steps includes sorting the rules in the first grammar data and the second grammar data alphabetically.

5. The method of claim 1, wherein the one or more transformational steps includes removing redundant parentheses from both the first grammar data and the second grammar data.

6. The method of claim 1, wherein the one or more transformational steps includes renaming all the rules in the first grammar data and the second grammar data according to a predetermined naming method.

7. The method of claim 1, wherein the one or more transformational steps includes sorting all deterministic alternatives in accordance with a predetermined sorting method.

8. The method of claim 1, wherein the one or more transformational steps includes two or more steps that are performed in a specific order.

9. The method of claim 1, further comprising, prior to applying one or more transformational steps to both the first and the second grammar, selecting one or more transformational steps to apply, wherein the selecting is based at least in part on a determination that two or more steps are performed in a specific order.

10. A system comprising:

one or more processors configured to include;

an accessing module to access first grammar data associated with a first grammar and second grammar data associated with a second grammar, wherein a grammar comprises one or more rules that define a programming language that corresponds to the grammar;

a transformation module to determine from the first grammar data and the second grammar data whether the first grammar and the second grammar correspond to the same programming language, wherein determining whether the first grammar and the second grammar correspond to the same programming language includes;

an application module to apply one or more transformational steps to both the first grammar data and the second grammar data;

a corresponding module to, after each transformational step, determine whether the first grammar data and the second grammar data correspond;

a comparison module, in accordance with a determination that the first grammar data and the second grammar data correspond, determine that the first grammar and the second grammar both correspond to the same programming language;

a step selection module to, in accordance with a determination that the first grammar data and the second grammar data do not correspond, selecting a next transformational step in the one or more transformational steps, wherein prior to selecting the next transformational step;

a determination module to determine whether there are any remaining transformational steps, and

a difference module to, in accordance with a determination that there are no remaining transformational steps, determine that the first grammar and the second grammar do not correspond to the same programming language.

11. The system of claim 10, wherein the comparison module further includes a determination module to determine whether the first grammar is an exact text correspond for the second grammar.

12. The system of claim 10, wherein the transformation module further includes a storing module to sort all deterministic alternatives in accordance with a predetermined sorting method.

13. A non-transitory computer-readable storage medium storing instructions that, when executed by the one or more processors of a machine, cause the machine to perform operations comprising:

accessing first grammar data associated with a first grammar and second grammar data associated with a second grammar, wherein a grammar comprises one or more rules that define a programming language that corresponds to the grammar;

determining from the first grammar data and the second grammar data whether the first grammar and the second grammar correspond to the same programming language, wherein determining whether the first grammar and the second grammar correspond to the same programming language includes;

applying one or more transformational steps to both the first grammar data and the second grammar data;

after each transformational step, determining whether the first grammar data and the second grammar data correspond;

in accordance with a determination that the first grammar data and the second grammar data correspond, determining that the first grammar and the second grammar both correspond to the same programming language; and

in accordance with a determination that the first grammar data and the second grammar data do not correspond, selecting a next transformational step in the one or more transformational steps, wherein prior to selecting the next transformational step;

determining whether there are any remaining transformational steps, and

in accordance with a determination that there are no remaining transformational steps, determining that the first grammar and the second grammar do not correspond to the same programming language.

14. The non-transitory computer-readable storage medium of claim 13, wherein determining whether the first grammar and the second grammar correspond comprises determining whether the first grammar is an exact text correspond for the second grammar.