I wonder whether context-free grammar (or what else?) can be used to implement "member of" structures, which describe that something is a member of something.

For example, I want to be able to infer the statement:

John Lennon is in Beatles.

The inferring process should return True since in the grammar John Lennon has been defined to be a member of the Beatles. If John Lennon weren't defined to be found in Beatles, I'd want to return False.

It does not look like a typical CFG product. Or could it be?

Or what kind of parsing and/or formal language technique is usable for this?

  • 1
    $\begingroup$ What do you mean by "implement"? Model the syntax of writing these things down? Note that what you have there is essentially prefix-form function application with arbitrarily many parameters, that is something that is part of the syntax of many programming languages and easily modelled with CFGs. Is your real question, can I express the semantics I want alongside parse trees of CFGs? $\endgroup$
    – Raphael
    Dec 18, 2015 at 16:23
  • 1
    $\begingroup$ I don't see where you see any "pattern matching". Can you explain? It seems to be that you are mixing syntax and semantics. $\endgroup$
    – Raphael
    Dec 18, 2015 at 16:35
  • $\begingroup$ @mavavilj, parsing is all about syntax and nothing about semantic, your query seems a non-sequitur. $\endgroup$ Dec 18, 2015 at 16:45

1 Answer 1


So you want to model expressions of the form

(function A B1 B2 B3 ... BN)

with a context-free grammar.

That's clearly possible; note that the term itself almost directly corresponds to a regular expression, i.e. you do not even need the full power of context-free grammars.

Consider this, for example (written in something like EBNF):

fct_appl = "(" fct_name set_name atom_name+ ")"

Here, X_name are tokens or other rules. If you separate parser and lexer, they would be lexer rules. If there are no syntactic differences between identifiers, you can use this

fct_appl = "(" ident ident ident+ ")"

This applies only to functions with one atomic and one list-type parameter, of course. You could also generalize to this:

fct_appl = "(" ident+ ")"

In any case, the semantics have to be defined elsewhere.

It does not really matter if you use programming-language style syntax like above, or natural-language style syntax like this:

my_membership = ident "is a" ident

This is all you need. Whether it's pre-, post- or infix, whether you use is a or , these are all design decisions that mostly go away after parsing¹ the syntax. Translate your parse tree into an AST and the information you get is the same: A is a B.

  1. Some nasty corner cases regarding ambiguity and left-/right-recursion may happen and depend on your choice of syntax.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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