解析演算法

句法分析的理論和實踐

報名參加課程

從這 4.5 小時的課程,你會學到

  • 無語境( Context-free  )語法
  • 抽象語法樹
  • 解析器生成器
  • 使用解析器生成器從頭開始建構一個完整的解析器
  • 自上而下的 LL 解析器
  • 自下而上的 LR 解析器
  • 逆向解析器
  • 左遞迴和左因子
  • 預測性遞迴下降解析器
  • LL(1)、LR(0)、SLR(1)、CLR(1)、LALR(1)分析器
  • Shift-reduce演算法
  • 語法工具:語言無關的解析器生成器

要求

  • 基本資料結構和演算法
  • 樹、圖、遍歷 ( Trees, graphs, traversal )
  • 對程式語言感興趣

課程說明

課程概述

解析或句法分析是設計和實現編譯器的首要階段之一。一個設計良好的程式語言的語法是一個很大的動機,為什麼使用者會喜歡和選擇正是你的語言。


經典編譯器學校和書籍中的 “解析器理論 “的問題是,這一理論通常被認為是 “太高階”,直接進入計算理論和形式化語法的複雜形式描述。因此,學生可能在解析階段就對構建編譯器失去興趣。

在描述解析器時經常看到的相反的問題是,只描述手動(通常是遞迴下降 recursive descent )解析的膚淺方法,使學生在理解自動解析器背後的實際技術時出現問題。


我相信,這種對解析理論的深入研究應該與實踐方法結合在一起,兩者並行不悖,可以在實踐中看到所有學到的理論材料。

在《解析精要》(又稱《解析演算法》)課上,我們深入研究瞭解析理論的不同方面,詳細描述了LL和LR解析器。然而,與此同時,為了使學習過程和理解變得簡單和有趣,我們從頭開始為一種完整的程式語言建立一個自動解析器,類似於 JavaScript 或 Python。

在這門課之後,你不僅能夠使用解析器生成器來建構程式語言的解析器,而且還能理解解析器生成器是如何在引擎蓋下工作的。

實現一種程式語言的解析器也會使你對其他程式語言的實際使用更加專業。

這門課是為誰準備的?

這門課是為任何好奇的工程師準備的,他們想獲得建立複雜系統的技能(為程式語言建立解析器是一項相當高階的工程任務!),並獲得建立這種系統的可轉移知識。

如果你對編譯器、直譯器和原始碼轉換工具特別感興趣,那麼這個班也適合你。

這門課的唯一前提是基本的資料結構和演算法:樹、列表、遍歷。

用什麼來實現?

由於我們建立的語言在語義上與 JavaScript 或 Python(當今最流行的兩種程式語言)非常相似,所以我們專門使用JavaScript–它優雅的多正規化結構結合了函數語言程式設計、基於類別和基於原型的OOP,非常適合於此。

許多工程師都熟悉JavaScript,所以它應該更容易立即開始編碼。為了生成自動解析器,我們使用了Syntax工具,它是一個語言無關的解析器生成器,並支援 Python、Ruby、C#、PHP、Java、Rust 等外掛。也就是說,這個解析器的實現可以很容易地轉移到你所選擇和喜歡的任何其他語言中。

注意:我們希望我們的學生能夠真正遵循、理解並自己實現解析器的每一個細節,而不是僅僅從最終的解決方案中複製貼上。該語言的完整原始碼可在影片講座中獲得,展示並指導如何建構特定的模組。

這門課有什麼具體內容?

這些講座的主要特點是:

  • 簡明扼要,直奔主題:每個講座都是自成一體,簡明扼要,描述與主題直接相關的資訊,不會在不相關的材料或講座上分散注意力
  • 動畫展示與現場編輯筆記相結合:這使得對主題的理解更加容易,並顯示出物件結構是如何(以及在什麼時候)連線的。靜態的幻燈片對複雜的內容根本不起作用。
  • 帶有作業的現場編碼課程端到端:完整的原始碼,從零開始,一直到最後,都在課堂的影片講座中呈現。

課程有哪些內容?

該課程分為四個部分,共22個講座,每個講座都有許多子主題。以下是內容和課程表。

第1部分。無語境( Context-free ) 語法和語言

在這一部分中,我們描述了不同的解析管道,談論形式化的語法,派生,什麼是模糊的和不理想的語法,並開始建立我們的程式語言。

第二部分:自上而下的LL解析

在這一部分中,我們詳細談論了自上而下的解析,描述了手動遞迴和回溯解析器,還深入探討了LL(1)解析演算法。

第三部分:自下而上的LR解析

在這一部分,我們描述了自下而上的解析器和LR解析演算法。同時,我們繼續建構我們的程式語言,分析shift-reduce衝突並修復它們。

第四部分:實踐和最終解析器

課程的最後一部分是完全實踐的,我們要完成我們的 Letter 程式語言,建立變數、函式、迴圈、控制結構、物件導向的程式設計,以及最後的解析器。

目標受眾

  • 任何好奇的工程師
  • 編譯器工程師

講師簡介

Dmitry Soshnikov 軟體工程師和講師 ( 更多講師線上課程介紹 )

Dmitry Soshnikov 是一名軟體工程師,也是一名有不同於電腦科學主題的講師。

他對教育充滿熱情,注重高品質的教育內容: 簡明扼要,並使用現場編輯筆記的動畫講座。

你會從 Dimitry 的課程學到:

  • 編譯器和直譯器: 建立一個程式語言
  • 垃圾收集器(自動記憶體管理)
  • 程式設計語言理論
  • Automata Theory: Building a RegExp machine
  • 自動機理論: 建立一個 RegExp 機器
  • 解析器理論: 實現一個編譯器編譯程式

英文字幕:有

  • 想要了解如何將英文字幕自動翻譯成中文? 請參考這篇 How-To

報名參加課程

Sponsored by Udemy

也許你會有興趣

找其它課程?試看看 Soft & Share 網站搜尋引擎

✍ 搜尋結果太多?可參考 Soft & Share 搜尋引擎使用技巧


追蹤 Soft & Share

幫我們個小忙!

這個網站採用 Akismet 服務減少垃圾留言。進一步了解 Akismet 如何處理網站訪客的留言資料

Powered by WordPress.com.

Up ↑

%d 位部落客按了讚: