9.3.语法

\(9.3.\)Grammars

1.Grammar introduction

  In the previous unit, we gain the ability to think about the program as a set of tokens, but the effect that we have a set of valid tokens doesn't imply that we have a valid program. It's not only the tokens that are important, the order of the tokens is critically important as well.

  And the artifact that defines in what order we can put tokens together legibly is referred to as grammar.

  • A grammar is a set of rules, describing how tokens can be combined to create valid language constructs

  Take the English language as an example:

  It's just a subset of English language, but is sufficiently rich to support plenty of inputs. Consider the sentence "The dog ate my homework":

  • 'The' is a det and 'dog' is a noun, so the sentence begins with a noun phrase.
  • 'ate' is a verb and 'my homework' is once again a noun phrase, so this subsentence is a verb phrase.
  • Taken together, we have a noun phrase followed by a verb phrase, therefore we have a legitimate sentence.

  In this example, we notice that grammar is indeed made of a set of rules. And these rules fall into two broad categories:

  1. Terminal rule: Its right-hand side consists of constants only.
  2. Non-terminal rule: Its right-hand side consists of names of other rules, and probably constants.

2.Jack grammar

  Let's focus on a subset of Jack language in which we have three possible statements: if, while, let:

  • We use * to indicate 0 or more.
  • We use | to denote choice.
  • We use ? to denote 0 or 1.

  And the process of determining if a given input conforms to a grammar is called prasing.

  Notice that in the process of doing this confirmation, we also uncover the entire grammatical structure of the given input, because we analyze how the input corresponds to the various components of the rule.