atitit.詞法分析原理 詞法分析器 (Lexer)

来源:http://www.cnblogs.com/attilax/archive/2016/04/23/5423472.html
-Advertisement-
Play Games

atitit.詞法分析原理 詞法分析器 (Lexer) 1. 詞法分析（英語：lexical analysis）1 2. ；實現詞法分析程式的常用途徑:自動生成,手工生成.[1] 2 2.1. 詞法分析程式的功能2 2.2. 如何描述詞素3 2.3. 單詞token3 2.4. Token的類型，根 ...


atitit.詞法分析原理 詞法分析器 (Lexer)

 

1. 詞法分析（英語：lexical analysis）1

2. ；實現詞法分析程式的常用途徑:自動生成,手工生成.[1] 2

2.1. 詞法分析程式的功能2

2.2. 如何描述詞素3

2.3. 單詞token3

2.4. Token的類型，根據程式設計語言的特點，單詞可以分為五類：關鍵字、標識符、常量、運算符、界符。以4

2.5. 詞法分析的第一階段即掃描器4

2.6. 詞法分析的第二階段評估器（Evaluator）5

2.7. 例如C語言程式段的詞法分析結果5

2.8. 最長原則6

2.9. 詞法單元的識別6

2.10. 不確定”（Nondeterministic Finite Automata ,NFA 8

2.11.  轉換圖(transition graph)的表示9

2.12. 詞法分析(3)---DFA10

2.13. 為什麼要NFA轉DFA12

2.14. 則表達式轉NFA13

2.15. 正則表達式如何轉換為NFA呢？有幾個公式(MLS2007[1])：13

2.16. 構造詞法分析器了。大致的流程如下：19

2.17. 常用的token scanner19

2.18. 詞法分析器也能檢測到源代碼裡邊的一些錯誤20

2.19. 參考21

 

1. 詞法分析（英語：lexical analysis）

是電腦科學中將字元序列轉換為單詞（Token）序列的過程。進行詞法分析的程式或者函數叫作詞法分析器（Lexical analyzer，簡稱Lexer），也叫掃描器（Scanner

 

詞法分析階段是編譯過程的第一個階段，是編譯的基礎。這個階段的任務是從左到右一個字元一個字元地讀入源程式，即對構成源程式的字元流進行掃描然後根據構詞規則識別單詞(也稱單詞符號或符號)。詞法分析程式實現這個任務。詞法分析程式可以使用Lex等工具自動生成。

詞法分析是編譯程式的第一個階段且是必要階段；詞法分析的核心任務是掃描、識別單詞且對識別出的單詞給出定性、定長的處理

 

 

一段對電腦來說豪無意義的字元串，經過語法分析後就得到了略微有意義的 Token 流。digit 就表示這個詞法單元對應的是數字，operator 則表示操作符，後面相應的數字和符號（粉色背景）就是詞素。同時，程式中一些不必要的空白、註釋也可以由詞法分析器來過濾掉，這樣，之後的語法分析等步驟處理起來就會容易得多

 

作者::  ★(attilax)>>>   綽號:老哇的爪子 （ 全名：：Attilax Akbar Al Rapanui 阿提拉克斯 阿克巴 阿爾 拉帕努伊 ） 漢字名：艾龍，  EMAIL:[email protected]

轉載請註明來源： http://www.cnblogs.com/attilax/

 

2. ；實現詞法分析程式的常用途徑:自動生成,手工生成.[1] 

儘管在某些情況下需要手工編寫詞法分析器，使用狀態模式,,一般情況下詞法分析器都用自動化工具生成。

 

2.1. 詞法分析程式的功能

完成詞法分析任務的程式稱為詞法分析程式或詞法分析器或掃描器。[1] 

從左至右地對源程式進行掃描，按照語言的詞法規則識別各類單詞，並產生相應單詞的屬性字。[1] 

 

詞法分析器通常不會關心單詞之間的關係（屬於語法分析的範疇），舉例來說：詞法分析器能夠將括弧識別為單詞，但並不保證括弧是否匹配。

 

。語法分析器讀取輸入字元流、從中識別出語素、最後生成不同類型的單詞。其間一旦發現無效單詞，便會報錯。

 

詞法分析器可以做諸如
1). 去掉註釋，自動生成文檔(c#中的///註釋)
2). 提供錯誤位置(可以通過記錄行號來提供)，當字元流變成詞法記號流以後，就沒有了行的概念
3). 完成預處理，比如巨集定義

 

 

2.2. 如何描述詞素

現在知道了詞法分析可以將詞素分割開來，那麼詞素是怎麼描述的？或者說，為什麼 12、+ 和 34 都是詞素，而 1、 2+3 和 4 就不是詞素呢？這就需要用到模式了。

模式（pattern）描述了一個詞法單元的詞素可能具有的形式。

也就是說，我定義了 digit 模式為“由一個或多個數字組成的序列”，和 operator 模式為“單個 + 或 * 字元”，詞法分析器就知道 12 是一個詞素，而 2+3 則不是詞素了。

現在，模式一般都是用正則表達式（regular expression）表示的，這裡所謂的正則表達式，與平常所說的正則表達式（例如 System.Text.RegularExpressions.Regex 類）形式完全相同，功能卻更有限，它只包含了字元串的匹配能力，而沒有分組、引用和替換的能力。簡單的舉個例子，a+ 這個正則表達式就表示“由一個或多個字元 a 組成的序列”。

 

2.3. 單詞token

這裡的單詞是一個字元串，是構成源代碼的最小單位。從輸入字元流中生成單詞的過程叫作單詞化（Tokenization），在這個過程中，詞法分析器還會對單詞進行分類。

分析詞素的同時還會同時記錄下這些詞素所在的行、列以便輸出錯誤信息供用戶查看，也會同時記錄詞素的類型。

 

{

"channel":0,

"charPositionInLine":15,

"inputStream":{"$ref":"$.tokenSource.charStream"},

"line":1,

"startIndex":15,

"stopIndex":15,

"text":"<EOF>",

"tokenIndex":2,

"type":-1

}

]

 

2.4. Token的類型，根據程式設計語言的特點，單詞可以分為五類：關鍵字、標識符、常量、運算符、界符。以

讀者可能對"單詞"感到有點疑惑，不明白到底什麼才是詞法分析中所說的"單詞"。試圖回答這個問題就必須瞭解幾個基本概念。這裡，引入幾個程式設計語言相關的名詞。

（1）標識符：用戶自定義的變數名、函數名等字元串。

（2）關鍵字：具有特殊含義的標識符。

（3）運算符：例如＋、－、*、/ 等。

（4）常量：例如3.24、92等。

（5）界符：具有特殊含義的符號，如分號、括弧等。

詞法分析的結果是識別出如下的單詞符號：

 

關鍵字

界符

標識符

運算符

常量

運算符

if

(

aa

&&

10

==

常量

界符

標識符

運算符

常量

界符

0

)

aa

=

100

;

 

這裡，讀者只需瞭解詞法分析的任務即可。其演算法實現將在第2章中詳述

 

2.5. 詞法分析的第一階段即掃描器

詞法分析的第一階段即掃描器，通常基於有限狀態自動機。掃描器能夠識別其所能處理的單詞中可能包含的所有字元序列（單個這樣的字元序列即前面所說的“語素”）。例如“整數”單詞可以包含所有數字字元序列。很多情況下，根據第一個非空白字元便可以推導出該單詞的類型，於是便可逐個處理之後的字元，直到出現不屬於該類型單詞字元集中的字元（即最長一致原則

2.6. 詞法分析的第二階段評估器（Evaluator）

 

 

，語法分析器需要第二階段的評估器（Evaluator）。評估器根據語素中的字元序列生成一個“值”，這個“值”和語素的類型便構成了可以送入語法分析器的單詞。一些諸如括弧的語素並沒有“值”，評估器函數便可以什麼都不返回。整數、標識符、字元串的評估器則要複雜的多。評估器有時會抑制語素，被抑制的語素（例如空白語素和註釋語素）隨後不會被送入語法分析器。

 

 

2.7. 例如C語言程式段的詞法分析結果

例2-1　C語言程式段的詞法分析結果見表2-1。

表2-1  詞法分析的單詞流

 

源程式字元流

詞法分析的邏輯結果

        int i,j;

         for (i=1;i<10;i++)

                  j=j+1;

int

i

,

j

;

for

(

i

=

1

;

i

< 

10

;

i

++

)

j

=

j

+

1

;

 

 

註意，表2-1的單詞流並不是詞法分析器真正的實際輸出結果，只是一種邏輯表示而已。更詳細的形式將在後續章節中討論。根據單詞的分類標準，可以將單詞作如下歸類，見表2-2。

表2-2  例2-1單詞流的分類

 

關  鍵  字

int

for

 

 

標識符

i

j

 

 

運算符

=

++

< 

+

常量

10

1

 

 

界符

,

;

(

)

 

這裡，讀者可能會有兩個疑問：

（1）為什麼"++"運算符不會分解為兩個"+"運算符呢？

（2）為什麼將"int i"分解為"int"和"i"，而不是"int i"呢？

 

最長原則

在實際編譯器設計中，任何詞法分析器都必須滿足一個原則，就是在符合詞法定義的情況下進行超前搜索識別。例如，當C語言詞法分析器讀入了一個字元"+"後，由於C語言中存在"++"、"+="運算符，那麼，詞法分析器會繼續讀入下一個字元。如果下一個字元是"+"或"="時，詞法分析器就將這兩個字元作為一個運算符。然而，如果下一個字元不是"+"或"="時，詞法分析器就將前一個字元"+"作為一個運算符記錄下來後，繼續識別下一個單詞。

根據這個原則，就可以解釋為什麼"int"沒有被識別為"i"、"n"、"t"了。根據C語言標識符（關鍵字只是有特殊含義的標識符）定義的規則，標識符必須以字母或下畫線開頭，後跟字母、數字、下畫線的任意組合。因此，當讀入"i"後，繼續讀入"n"，由於"in"是合法的標識符，則繼續讀入"t"。直到讀到"　"時，發現"int "不滿足標識符的定義，則將"int"記錄下來即可。

 

2.8. 最長原則

不過，詞法分析器的設計難度很大程度上依賴於程式設計語言本身的規範

在設計一門程式設計語言時，應該儘可能避免關鍵字非保留字、空格忽略等類似情況的發生，否則將給詞法、語法分析造成相當的障礙

 

 

2.9. 詞法單元的識別

         某些狀態為接受狀態或最終狀態，表明已經找到一個詞素。

       1）關係符轉換圖

       2）保留字和標識符轉換圖

      3）無符號樹轉換圖

       4）空白轉換圖

 

 

2.10. 不確定”（Nondeterministic Finite Automata ,NFA

有窮自動機

        1）有窮自動機可用作描述在輸入串中識別模式的過程，因此也能用作構造掃描程式。當然有窮自動機與正則表達式之間有著很密切的關係

        2）有限自動機分成確定的和不確定的兩種情況。“不確定”（Nondeterministic Finite Automata ,NFA）的含義是，存在這樣的狀態，對於某個輸入符號，它存在不只一種轉換。 確定的和不確定的有限自動機都正好能識別正規集，也就是它們能識別的語言正好是正規式所能表達的語言。

假定一個輸入符號(symbol)，可以得到2個或者2個以上的可能狀態，那麼這個finite automaton就是不確定的，反之就是確定的。例如：

這就是一個不確定的無限自動機，在symbol a輸入的時候，無法確定狀態應該轉向0，還是1

不論是確定的finite automaton還是非確定的finite automaton，它們都可以精確的描述正規集(regular sets)
我們可以很方便的把正規表達式(regular expressions)轉換成為不確定 finite automaton

 

下麵關於FA和NFA的描述是抄襲AMRJ2010[1]的：

轉換的核心是被稱為有窮自動機(finite automata)的表示方法。這些自動機在本質上是與狀態轉換圖類似的圖，但有如下幾點不同：

· 有窮自動機是識別器，它們只能對每個可能的輸入串簡單的回答“是”或“否”。

 

 

2.11. 

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Hibernate註解----類級別註解以及屬性註解詳解----圖片版本
    這篇文章是我在慕課網上學習Hibernate註解的時候進行手機以及整理的筆記。 今天把它分享給大家，希望對大家有用。可以進行收藏，然後需要的時候進行對照一下即可。這樣能起到一個查閱的作用。 本文主要講解的內容簡介 ： 第1章 類級別註解 1-1 本章簡介 1-2 準備工作 1-3 @Entity註解 ...
  • 單詞倒排
    #include<stdio.h>int main(){ int i,j; int word=0,num=0;//新單詞標記，單詞下標 char str[100],s[50][20]={0},c; gets(str);//輸入字元串（多個單詞） for(i=0;(c=str[i])!='\0';i+ ...
  • 343. Integer Break -- Avota
    問題描述: Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maxim ...
  • collections中可命名元組和隊列
    一丶可命名元組（nametuple） ...
  • PHP中的include和require
    1.include語句 使用include語句可以告訴PHP提取特定的文件，並載入它的全部內容 1 <?php 2 inlude "fileinfo.php"; 3 4 //此處添加其他代碼 5 ?> 使用include語句可以告訴PHP提取特定的文件，並載入它的全部內容 1 <?php 2 inl ...
  • PHP舊系統基於命名空間重構經驗
    命名空間其實只是一個形式，最終目的是重構代碼，但這個過程想要一蹴而就是不可能的。 一開始給了一個偽命題：基於ThinkPHP的重構（不要為什麼）。經過一段的實踐，發現這是一個大錯特錯的思維方式，其中遇到的坑在此略過不表。 首先，不要想著全盤基於命名空間重寫，而應該是基於局部的。 最終思考後的結果，是 ...
  • java事務（三）——自己實現分散式事務
    在上一篇《java事務（二）——本地事務》中已經提到了事務的類型，並對本地事務做了說明。而分散式事務是跨越多個數據源來對數據來進行訪問和更新，在JAVA中是使用JTA(Java Transaction API)來實現分散式的事務管理的。但是在本篇中並不會說明如何使用JTA，而是在不依賴其他框架以及j ...
  • HTTP協議
    HTTP協議（HyperText Transfer Protocol，超文本傳輸協議）是網際網路上應用最為廣泛的一種網路傳輸協議，所有的WWW文件都必須遵守這個標準。 HTTP是一個基於TCP/IP通信協議來傳遞數據（HTML 文件, 圖片文件, 查詢結果等）。 HTTP協議工作於客戶端-服務端架構為 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類