2

As someone trained in neither, how could you explain the analogies between context free grammars / languages and certain programming languages in computer science? Have I misunderstood whether there is actually an analogy that merits interplay? What are examples of these computer languages?

Keep in mind my training is in mathematics / mathematical physics, so don’t be afraid to give a “more than surface level” explanation! I’ve been quite interested in some interplay between linguistics and information theory, given the deep interplay between information theory and physics!

Improve this question
7
  • There are many applications of information in linguistics, though I don't think CFGs are related to any of them
    – WavesWashSands
    Commented Oct 9, 2019 at 16:29
  • This looks like a question about theoretical computer science, try Theoretical Computer Science or Computer Science.
    – Sir Cornflakes
    Commented Oct 10, 2019 at 16:12
  • I'm voting to close this question as off-topic because this question is not about linguistics at all, it uses the word "language" for a formal language.
    – Sir Cornflakes
    Commented Oct 10, 2019 at 16:13
  • 1
    @jknappen The Chomsky hierarchy is one of the first things taught in linguistics courses on syntactic theories. There is a slew of academic literature on this topic published by linguists. The question is definitely on-topic here.
    – prash ♦
    Commented Oct 12, 2019 at 7:48
  • @prash The main questions asked are about computer languages, and the Chomsky hierarchy is taught in Computer Science courses as well.
    – Sir Cornflakes
    Commented Oct 12, 2019 at 13:55

2 Answers 2

Reset to default
4

Have I misunderstood whether there is actually an analogy that merits interplay?

No, and analogies will not help. These grammars are called "context-free" but that has nothing to do with the context of meanings of words. Instead, it refers to abstract mathematical structures. There are various kinds of term rewriting rules or tree rewriting rules. The nature of these rules determine the nature of the trees that can be generated.

There is a hierarchy (called the Chomsky hierarchy) for the complexity of trees that can be generated by term rewrite rules. "Context-free" is the name of one of the levels in the hierarchy. Formal language theory: refining the Chomsky hierarchy gives an overview of the topic.

Improve this answer
0

To add to the previous answer: context free grammars are the basis of the modern theory of computation. More specifically:

  • All programming languages can be described using context free grammars, although it is not always beneficial from the practical viewpoint. The languages like Lisp and its modern offshoots (Clojure, Haskell, etc.) are more explicitly grounded in CFG, but are also viewed more as suitable for theoretical computer science than for practical programming.
  • Practical implementation of any computer language includes a compiler, which includes a parser: the goal of which is essentially translating a program into a syntax tree. Numerous parsing algorithms have been developed for this purpose.
  • Finally, CFG plays important role in theoretical computer science, where it is shown to be equivalent to push-down automata, and eventually allows assessing complexity and computability of problems.
Improve this answer
2
  • Whoah, there's some statements that require revision or clarification here, IMO. Haskell is not an offshot of Lisp, except that it it is functional -- but purely, which Lisps never were. Both Haskell and Clojure are very much used in practical programming (as opposed to, say, Agda). And I don't see why they are "grounded in CFG"; there might exist BNFs for those languages, which others lack, but that's still a weird thing to say. Not "every language includes a compiler" -- interpretation is perfectly fine. Not always a tree representation is required.
    – phipsgabler
    Commented May 22, 2020 at 10:20
  • Also, the border for programming language implementations is a bit fuzzy. Sometimes, there's a context free description being used in lexical analysis, but this is followed by an additional syntactic parse to e.g., resolve ambiguities, operator precedence, check for contextual keywords, etc... It's not clear which "level" of the grammatical analysis you'd call context-free then. See here for a couple of examples.
    – phipsgabler
    Commented May 22, 2020 at 10:22

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.