Please enable JavaScript.

Coggle requires JavaScript to display documents.

Chapter 3 描述語法(syntax) (描述語法的形式化方法 (BNF and Context-Free Grammars (BNF (B…

- - - - 說明
        
        識別設備會讀進input字串，並決定其是否屬於該語言
        
        e.g. 語法分析編譯器的一部分
    - - 說明
        
        產生句子的設備
        
        可決定特定句子的句法是否正確
- - - - 說明
        
        是為語言生成器，用來描述自然語言的句法
        
        用來定義 context-free languages
    - - 特點
        
        是可用來描述其他語言的元語言(metalanguage)
        
        在BNF中，抽象化被用來表示句法結構的類別，像是句法變數(又被稱為nonterminal symbols)...等
        
        等同 context-free grammars
      - 文法要素 (:fire::fire::fire: 3-13圖片)
        
        Non-terminals : <XXX>
        
        Terminals: lexemes and tokens (if, then)
        
        Grammar: 一系列的規則
        
        Start symbol: 特別的nonterminal
      - B.N.F.文法符號說明
        
        “::=＂:表示“定義為＂，相當於->。
        
        “{}＂:表示出現0次,1次,...。(EBNF才有)
        
        “[]＂:表示出現0次或1次。(EBNF才有)
        
        “|”:表示“OR”。
        
        ”< >＂:表示非終端符號。
      - 規則
        
        分類
        
        LHS : 左手邊
        
        RHS : 右手邊
        
        Symbol
        
        terminal
        
        nonterminal
        
        文法是一組由規則所組成的有限非空集合
        
        抽象概念(非終結符號)可以有多個RHS
        
        Nonterminal可有多個不同的定義
        
        多重定義可以被用單一規則表示(用OR)
      - Derivation(展開)
        
        Derivation中的每一串符號都是一個 sentenial form
        
        sentence
        
        一個只含 terminal symbol的 sentenial form
        
        leftmost/rightmost derivation
        
        每次要從最左邊還是最右邊展開
        
        展開的次序不一定要相同
      - Parse Tree
        
        內部節點 : nonterminal
        
        樹葉節點 : terminal symbol
      - 語法歧義(Ambiguity)
        
        定義
        
        一個grammar所產生的 sentenial form 可以生成至少兩棵的parse tree(:fire::fire::fire: 3-23圖片)
        
        說明
        
        一個運算式用parse tree展開後，較底層的operator有較高運算優先權
      - 規範Operator的運算次序
        
        讓低優先權的運算先展開(先展開會後運算)
        
        Associativity (聯結性)
        
        說明
        
        當運算式中的兩個operator擁有相同運算優先權時，到底先算哪一個?
        
        e.g. B+C+A 該左結合還是右結合?
        
        對於某些運(如次方)，左結合與右結合的運算結果不同
        
        如何規範
        
        左遞迴
        
        e.g. <expr> -> <expr> + const | const
        
        規範左結合
        
        推論規則中LHS出現在RHS最前面
        
        右遞迴
        
        推論規則中LHS出現在RHS最後
        
        e.g. <expr> -> const + <expr> | const
        
        規範右結合
    - - 最廣泛被用來描述程式語言句法的方法
  - - - 增強了BNF的可讀性以及易寫性`，但並沒有增強BNF的描述力。
      - 符號
        
        [ ] : 出現0或1次 (p.3-32)
        
        ( | ) : 多重選擇
        
        { } : 重複0或多次，可用來簡化recursive版本的BNF
        
        :fire::fire::fire:p.32~36 example