What is the meaning of context free?
This is in light of a post I made many days ago concerning creating a semantic checker using Lex and/or Yacc.
What does the term context-free mean when talking about programming languages? What is it that makes a programming language context-sensitive?
For example, why is C++ context-sensitive and Java is (or so I am told) context-free?
-- Ivyn --
Context-free is a term that comes from the systematic study of grammars. This study was first done as part of linguistics, but quickly was picked up by people writing some of the first compilers for programming languages. Further study has shown that grammar classes correspond with different levels of computational difficulty, and so they''ve been adopted as part of the core of computer science.
There are three primary classes of grammars: regular, context-free, and context-sensitive.
Regular grammars are the simplest. If you''re familiar with BNF, regular expressions are those which can be expressed with only expressions with a single non-terminal, on only one side of the terminal expressions in the production. That is, they can be expressed in productions of this form:
A ::= aB
B ::= aB | bB | c
If the start symbol for this grammar was A, then this grammar can produce any string that starts with an a, ends with a c, and has only a''s and b''s in between.
This is, as the name suggests, equivalent to the class of strings produced (and recognized) by regular expressions. The combination of concatenation, alternation, and repetition (kleene closure) is equivalent to regular grammars.
Regular grammars can be recognized by finite state machines... Those are machines which have a limited amount of storage (current state only), and simple computation. The only computation is changing states based on an input. Whether a string matched a given regular grammar is determined by the state the FSM is in when the computation ends. This is a very limited class of computations, but much can be done within it.
The next major category of grammars is context-free. A grammar is context-free if it can be described in BNF form with only the single non-terminal on the left side of the production. That is, things you normally see in BNF form. Context-free grammars are necessary for things like recognizing nested grammatical structures (the code inside {} pairs in C or Java, for instance.)
Context-free grammars can be recognized by pushdown automata (PDAs). A pushdown automaton is similar to a (non-deterministic) finite state machine, but adds a limited form of infinite memory. A PDA has, in addition to the current state, an infinite stack. It uses the top element of the stack in determining state transitions, in addition to the current state. Transitions in a PDA are also expanded. The stack can be altered as well, adding an element, removing the top element, or changing the top element.
PDAs are a relatively powerful computational construct. Many problems can be solved by PDAs.
The third major class of grammars is context-sensitive. Context-sensitive grammars are those which can be expressed in BNF, using multiple symbols on the LHS of the productions. For instance:
aAa ::= aaa
bAb ::= bbb
The productions for the non-terminal symbol A is context-sensitive, explaining the name for the grammar type. My example is quite anemic, but there are grammars which are context-sensitive which cannot be expressed in a context-free system.
Context-sensitive grammars can be recognized by Turing machines. I''ll assume you know what a Turing machine is, so I''ll skip the description there.
Because of the famous halting problem, it is known that there are problems that even a Turing machine cannot solve. Because of the equivalence between context-sensitive grammars and Turing machines, there must be another, most complicated class of grammars. Those grammars are undecidable, just as all problems that cannot be solved by a Turing machine are.
Most programming languages are kept context-free, if possible, because it simplifies parsing. Since PDAs are rather inefficient in practice, most programming languages are also kept to more restricted grammar classes like LL(k) or LALR(1), which can be recognized by more efficient means.
Java is definitely context-free. I''m not sure about C++. I suspect that if it''s not, it''s related to either templates or the preprocessor. MKH''s remark about function overloading is not relevant... That''s semantic, not syntactic. Overloaded functions are no more difficult to recognize syntactically than non-overloaded functions.
For more information, find a book or take a class about automata theory. A compilers course (or book) would also cover some of this, with more detail on the grammar types like LR, LL, and LALR.
There are three primary classes of grammars: regular, context-free, and context-sensitive.
Regular grammars are the simplest. If you''re familiar with BNF, regular expressions are those which can be expressed with only expressions with a single non-terminal, on only one side of the terminal expressions in the production. That is, they can be expressed in productions of this form:
A ::= aB
B ::= aB | bB | c
If the start symbol for this grammar was A, then this grammar can produce any string that starts with an a, ends with a c, and has only a''s and b''s in between.
This is, as the name suggests, equivalent to the class of strings produced (and recognized) by regular expressions. The combination of concatenation, alternation, and repetition (kleene closure) is equivalent to regular grammars.
Regular grammars can be recognized by finite state machines... Those are machines which have a limited amount of storage (current state only), and simple computation. The only computation is changing states based on an input. Whether a string matched a given regular grammar is determined by the state the FSM is in when the computation ends. This is a very limited class of computations, but much can be done within it.
The next major category of grammars is context-free. A grammar is context-free if it can be described in BNF form with only the single non-terminal on the left side of the production. That is, things you normally see in BNF form. Context-free grammars are necessary for things like recognizing nested grammatical structures (the code inside {} pairs in C or Java, for instance.)
Context-free grammars can be recognized by pushdown automata (PDAs). A pushdown automaton is similar to a (non-deterministic) finite state machine, but adds a limited form of infinite memory. A PDA has, in addition to the current state, an infinite stack. It uses the top element of the stack in determining state transitions, in addition to the current state. Transitions in a PDA are also expanded. The stack can be altered as well, adding an element, removing the top element, or changing the top element.
PDAs are a relatively powerful computational construct. Many problems can be solved by PDAs.
The third major class of grammars is context-sensitive. Context-sensitive grammars are those which can be expressed in BNF, using multiple symbols on the LHS of the productions. For instance:
aAa ::= aaa
bAb ::= bbb
The productions for the non-terminal symbol A is context-sensitive, explaining the name for the grammar type. My example is quite anemic, but there are grammars which are context-sensitive which cannot be expressed in a context-free system.
Context-sensitive grammars can be recognized by Turing machines. I''ll assume you know what a Turing machine is, so I''ll skip the description there.
Because of the famous halting problem, it is known that there are problems that even a Turing machine cannot solve. Because of the equivalence between context-sensitive grammars and Turing machines, there must be another, most complicated class of grammars. Those grammars are undecidable, just as all problems that cannot be solved by a Turing machine are.
Most programming languages are kept context-free, if possible, because it simplifies parsing. Since PDAs are rather inefficient in practice, most programming languages are also kept to more restricted grammar classes like LL(k) or LALR(1), which can be recognized by more efficient means.
Java is definitely context-free. I''m not sure about C++. I suspect that if it''s not, it''s related to either templates or the preprocessor. MKH''s remark about function overloading is not relevant... That''s semantic, not syntactic. Overloaded functions are no more difficult to recognize syntactically than non-overloaded functions.
For more information, find a book or take a class about automata theory. A compilers course (or book) would also cover some of this, with more detail on the grammar types like LR, LL, and LALR.
A Turing machine is a formal model of computation, believed to be capable of computing anything that any model can compute. It was, I believe, the first formal model of computation to be worked out. It was created by Alan Turing in an attempt to determine whether there were problems that couldn''t be solved by a computer.
A Turing machine is a very simple device. It consists of a finite number of internal states, a read/write head head over an infinitely long tape, and a finite set of rules. The rules are 5-tuples of the form: (current state, current symbol, next state, next symbol, move direction).
Computation works by the following process:
1. Put the Turing machine into its initial state, with the tape in its initial position. These values are determined arbitrarily. (Doesn''t really matter.)
2. Given the current state, and symbol on the tape, find a rule that matches. (Should usually be unique, but a non-deterministic Turing machine would be equivalent.) If no rule matches, the computation is done.
3. Change to the next state given by the rule in use.
4. Write the next symbol given by the rule in use to the tape, in the current position.
5. Move the tape in the direction given by the rule.
6. Go to step 2.
The tape has three purposes... First, it serves as input. Second, it is storage space during the computation. Finally, it is where the output of the finished computation is stored. The symbols on the tape come from a limited set, which usually includes a blank symbol for simplicity.
For every problem that there are existing solutions for, it is believed that a Turing machine which solves the problem exists. Certainly one has been found for every problem that has been checked.
This includes the interesting problem of "Given a turing machine M, and an initial tape T, determine the output of M''s calculation given T."
The Turing machine that solves that problem is known as the universal Turing machine. That name should be no surprise, as that Turing machine can solve anything any Turing machine can.
So then the big question was asked: "Is there anything a universal Turing machine can''t solve?"
To answer this, Turing came up with the halting problem: "Given a Turing machine M, determine if that Turing machine will halt (finish computations) on a particular input."
This problem cannot be solved by a Turing machine. A simple (probably over-simplified) proof by contradiction follows:
Assume there exists a Turing machine M which can solve the halting problem.
Construct from M a Turing machine M'' which takes as input a Turing machine. M'' will run forever if the input turing machine will halt on all computations. Otherwise M'' will halt.
Run M'', giving it M'' as the Turing machine, with M'' as the input.
This run of M'' will run forever if M'' halts given M''. It will halt if M'' runs forever given M''.
That is a contradiction... Hence, the initial assumption must be wrong. M must not exist.
Therefore, there are problems a Turing machine can''t solve. And since we''ve yet to find a computational system more powerful than a Turing machine, it''s believed that those problems are just unsolvable.
For an example of a Turing machine in action, check out this applet: http://www.igs.net/~tril/tm/tm.html
It''s a little annoying to use at first, but it has some great examples built in.
A Turing machine is a very simple device. It consists of a finite number of internal states, a read/write head head over an infinitely long tape, and a finite set of rules. The rules are 5-tuples of the form: (current state, current symbol, next state, next symbol, move direction).
Computation works by the following process:
1. Put the Turing machine into its initial state, with the tape in its initial position. These values are determined arbitrarily. (Doesn''t really matter.)
2. Given the current state, and symbol on the tape, find a rule that matches. (Should usually be unique, but a non-deterministic Turing machine would be equivalent.) If no rule matches, the computation is done.
3. Change to the next state given by the rule in use.
4. Write the next symbol given by the rule in use to the tape, in the current position.
5. Move the tape in the direction given by the rule.
6. Go to step 2.
The tape has three purposes... First, it serves as input. Second, it is storage space during the computation. Finally, it is where the output of the finished computation is stored. The symbols on the tape come from a limited set, which usually includes a blank symbol for simplicity.
For every problem that there are existing solutions for, it is believed that a Turing machine which solves the problem exists. Certainly one has been found for every problem that has been checked.
This includes the interesting problem of "Given a turing machine M, and an initial tape T, determine the output of M''s calculation given T."
The Turing machine that solves that problem is known as the universal Turing machine. That name should be no surprise, as that Turing machine can solve anything any Turing machine can.
So then the big question was asked: "Is there anything a universal Turing machine can''t solve?"
To answer this, Turing came up with the halting problem: "Given a Turing machine M, determine if that Turing machine will halt (finish computations) on a particular input."
This problem cannot be solved by a Turing machine. A simple (probably over-simplified) proof by contradiction follows:
Assume there exists a Turing machine M which can solve the halting problem.
Construct from M a Turing machine M'' which takes as input a Turing machine. M'' will run forever if the input turing machine will halt on all computations. Otherwise M'' will halt.
Run M'', giving it M'' as the Turing machine, with M'' as the input.
This run of M'' will run forever if M'' halts given M''. It will halt if M'' runs forever given M''.
That is a contradiction... Hence, the initial assumption must be wrong. M must not exist.
Therefore, there are problems a Turing machine can''t solve. And since we''ve yet to find a computational system more powerful than a Turing machine, it''s believed that those problems are just unsolvable.
For an example of a Turing machine in action, check out this applet: http://www.igs.net/~tril/tm/tm.html
It''s a little annoying to use at first, but it has some great examples built in.
For a great example of an implementation of a Turing Machine, you must check The Brainfuck Compiler. It''s great!
Good God, c_wraith your excellent replies are worth a good article on its own! Thank you for taking the time to type all that knowledge up. You really seem to know what you''re talking about and this has helped me greatly.
Only thing I''m confused about now is the difference between ''semantic'' and ''syntactic''?
-- Ivyn --
Only thing I''m confused about now is the difference between ''semantic'' and ''syntactic''?
-- Ivyn --
syntactic is the actual grammar, whether it is spelled wrong.
ex: Int number =1;
char letter;
leter =''r'';
as you can see Int is a syntatic error because it is spelled wrong.
when declaring an int you type "int" not "Int".
also after i declared the variable "letter", i initialized with ''r'' but i spelled the variable wrong, it should be "letter" not "leter".
semantic is how the syntax is used [properly] (the error is usually a logic error, in a programming perspective)
ex: while (number = 10) {
cout << number << "!" << endl;
number--;
}
the error here is "number = 10" though syntatically it is correct semantically it is not. the while loop will be infinite. because number is assigned a nonnegative number which be equal true always.
the correct condition should be "number == 10" not "number = 10".
that way the loop checks to see if number is equal (==) to 10 not assigned (=) 10.
i''m pretty sure c_wraith will have a better explaination but i wanted to put my two cents in. (please no unneeded insults.)
ex: Int number =1;
char letter;
leter =''r'';
as you can see Int is a syntatic error because it is spelled wrong.
when declaring an int you type "int" not "Int".
also after i declared the variable "letter", i initialized with ''r'' but i spelled the variable wrong, it should be "letter" not "leter".
semantic is how the syntax is used [properly] (the error is usually a logic error, in a programming perspective)
ex: while (number = 10) {
cout << number << "!" << endl;
number--;
}
the error here is "number = 10" though syntatically it is correct semantically it is not. the while loop will be infinite. because number is assigned a nonnegative number which be equal true always.
the correct condition should be "number == 10" not "number = 10".
that way the loop checks to see if number is equal (==) to 10 not assigned (=) 10.
i''m pretty sure c_wraith will have a better explaination but i wanted to put my two cents in. (please no unneeded insults.)
quote:Original post by Alpha_ProgDes
because number is assigned a nonnegative number which be equal true always.
Just a little niggle, but negative numbers are also true. Zero is false.
Syntax refers to structure, semantics refers to meaning.
true. bad of me to overlook that fact.
oluseyi could run over to the "extern" topic that was just up?
i asked you to answer a question for me. thanks.
oluseyi could run over to the "extern" topic that was just up?
i asked you to answer a question for me. thanks.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement