0
$\begingroup$

I am trying to write a mini parser for a simple language whose specification is as follows:

A search term is represented by. Both searchkey and searchvalue is a word formed by using alphanumeric characters.

<searchkey> <searchoperator> <search value>

: represents the exact match(similar to "=").
ex :

response:success

multiple search terms can be combined with AND & OR operator. ex.

response:sucess AND extension:php

By default AND has higher precedence than OR but this can be changed by grouping the search terms in a round bracket. ex:

response:sucess AND (extension:php OR extension:css)

along with : other valid operators search operators are >, >=, <, <= . ex.

time >= 2020-01-09 AND response:success OR os:windows

A search term could be preceded with NOT keyword to do the negation. ex.

response:success AND NOT os:windows

I have written this grammar in ebnf notation :

<exp> ::= <exp> " OR " <exp> | <logical_and>
<logical_and> ::= <exp> " AND " <exp> | <logical_not>
<logical_not> ::= " NOT " <logical_not> | <term>
<term> ::= "(" <exp> ")" | <atom>
<atom> ::= <word> <op> <word>
<op> ::= ">" | ">=" | ":" | "<" | "<="
<word> ::= ("a" | "b" | "c" | "d" | "e" | "f" | "g"
                      | "h" | "i" | "j" | "k" | "l" | "m" | "n"
                      | "o" | "p" | "q" | "r" | "s" | "t" | "u"
                      | "v" | "w" | "x" | "y" | "z")+

But originally I had come up with this grammar.

<expr> ::= <or>
<or> ::= <and> (" OR " <and>)*
<and> ::= <unary> ((" AND ") <unary>)*
<unary> ::= " NOT " <unary> | <equality>
<equality> ::=  (<word> ":" <word>) | <comparison>
<comparison> ::= "(" <expr> ")" | (<word> (" > " | " >= " | " < " | " <= ") <word>)+
<word> ::= ("a" | "b" | "c" | "d" | "e" | "f" | "g"
                      | "h" | "i" | "j" | "k" | "l" | "m" | "n"
                      | "o" | "p" | "q" | "r" | "s" | "t" | "u"
                      | "v" | "w" | "x" | "y" | "z")+

is there any difference if I choose one over another? Can there exist multiple grammars for a language? Is there any formal way to generate grammar for a language? this is a small language so its easy to get the grammar intuitively by tweaking it but what if the langue specification is huge?

$\endgroup$
  • 1
    $\begingroup$ You don't have a language specification before you write the EBNF. All you have is a few examples. A few examples is not a specification. So your question is trying to nail jelly to the wall. If you had a formal specification, you might be able to mechanically convert it to a different formal specification (such as the subset of EBNF which is formally complete). Or you might not; it would depend on the nature of the specifications. But there's no formal mechanism which can produce a formal specification from a language whose vague contours you sketch in the air. $\endgroup$ – rici May 24 at 20:04
  • $\begingroup$ But to answer your concrete question: Yes, any language has an unlimited number of possible grammars. It is not, in general, possible to verify whether two different grammars derive the same language. If you just want to recognise whether a sentence is in a language, it doesn't matter which of the grammars for that language you use, but if you want to parse the language in order to reveal the syntactic structure of a valid text, then your grammar should reflect the syntactic structuring you have in mind, and not all of them do. $\endgroup$ – rici May 24 at 20:08
  • $\begingroup$ @rici first of all thank you very much for taking the time and explaining, i should have made explicit in the question about the rules of my language, but your last lines "if you want to parse the language in order to reveal the syntactic structure of a valid text, then your grammar should reflect the syntactic structuring you have in mind, and not all of them do" clears most of my doubt i had. $\endgroup$ – anekix May 24 at 20:14
  • $\begingroup$ @rici i have modified the original question to include the rules of this mini language . i hope its clear now. $\endgroup$ – anekix May 24 at 20:26
2
$\begingroup$

Your informal description of your language could certainly be made more precise, in the same way as you could make the description of any (mathematical) set more precise until you've written the description out in mathematical notation. In that sense, EBNF is similar to what you get when you recast an informal description of a language into a mathematical formalism. (EBNF doesn't quite qualify, but the BNF formalism which inspired EBNF is a precise formalism.)

In between the formal description of a language and the practical question of building a parser for the language, a number of practical issues need to be dealt with, many of them having to do with the way a string of characters is grouped into meaningful tokens in the concrete representation of the language. In other words, questions like "where can spaces and newline characters be placed?" "Can I insert comments into an expression?" and so on. It's possible to write these into a formal description of a language, but the end result is often not particularly useful for the casual reader because the high-level structure of the language is overwhelmed by pesky details.

I note in passing that your grammar requires that AND and NOT appear with precisely one space preceding and following, while no spaces are allowed around the >= operator (and friends). That means that several of your examples don't match the EBNF. For example, time >= 2020-01-09 would have to be written as time>=2020-01-09 and response:success AND NOT os:windows as response:success AND NOT os:windows (with two spaces between AND and NOT). I doubt that was your intent, and I don't say this to criticise; just to point out how tricky it can be to get the details right, so that it can actually be used to construct a concrete parser, and still make the grammar usable for human readers. The usual approach is to separately formalise the division of the text into lexemes ("tokens") and the syntactic structure of the language, which treats the inputs as a stream of tokens rather than as a stream of undifferentiated characters. That's by no means formally necessary, and a lot of the applications of EBNF do in fact attempt to be precise to the character level, but a close examination of these EBNF applications might reveal the practical limitations of this strategy.

As I said in a comment, for any language for which a context-free grammar exists, there are an unlimited number of other context-free grammars which derive the same language. However, the question of whether two context-free grammars derive the same language is undecidable; no algorithm exists which can always correctly make that determination. Consequently, it is also impossible to enumerate all the grammars which could derive a given language (however that language is given).

In addition, there are competing mathematical formalisms which could be used to describe a language. After all, a language is a set, and any mathematical expression which precisely defines a set is a possible formal language description. (Some of these will be more practically usable than others.) So there's no way to say whether a procedure exists to generate a description in one formalism from a description in another formalism without know what, exactly, the nature of the two formal systems is. Sometimes it will be possible, other times not.

If you only want to know if a given text is in a language, then any of the unknowable infinitude of possible grammars for that language will suffice, although it's better if the grammar formalism used is computationally tractable. But most of the time, you don't just want to know that a text is in a language. (A C "compiler" whose only possible output is one of the messages "yes, that is a well-formed C program" and "no, that is not a well-formed C program" is unlikely to attract many paying customers, even if its judgement is 100% correct.) In most applications, you want to parse the language in order to reveal the syntactic structure of a valid text. To do that, your grammar should reflect the syntactic structuring you have in mind, and not all of the possible grammars for the language do.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thankyou for such a detailed answer . It got me excited on reading the formal language theory more in a detailed and structured way :) as of now my doubts have been cleared. $\endgroup$ – anekix May 24 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.