now that we have begun to connect syntax and semantics, let's do a little exercise about what would happen if we did NOT
Posted: Mon Jun 06, 2022 1:50 pm
now that we have begun to connect syntax and semantics, let's do
a little exercise
about what would happen if we did NOT do that in ONE
computation.
We can have a context free grammar
for n_1n_2_n_3v_1_v_2v_3, etc., where indices indicate
which n is argument of which v.
The form part of the question is actually context-free, same as
a^nb^n. It is the semantics which causes
us to think of it as a non-context-free language.
Now, suppose that we decided we can live with multiple
computations. We will compute the syntax first, then
semantics.
In this context, we can write a context-free grammar for n^mv^m,
m >=0.
Suppose that this grammar gives us a tree that we can
manipulate later, as a program, if you like.
Question: How can this program make sure that
first n is for first v, then second n for second v, etc, in a tree
of finite length?
Write in pseudo-code if you like.
a little exercise
about what would happen if we did NOT do that in ONE
computation.
We can have a context free grammar
for n_1n_2_n_3v_1_v_2v_3, etc., where indices indicate
which n is argument of which v.
The form part of the question is actually context-free, same as
a^nb^n. It is the semantics which causes
us to think of it as a non-context-free language.
Now, suppose that we decided we can live with multiple
computations. We will compute the syntax first, then
semantics.
In this context, we can write a context-free grammar for n^mv^m,
m >=0.
Suppose that this grammar gives us a tree that we can
manipulate later, as a program, if you like.
Question: How can this program make sure that
first n is for first v, then second n for second v, etc, in a tree
of finite length?
Write in pseudo-code if you like.