Lexer란 무엇입니까?
56144 단어 rustlanguagedesignparsingcompilers
이것은 해석의 임무다.해석은 컴퓨터 과학에서 광범위하고 깊이 있는 연구 분야로 형식적으로 말하자면 주어진 문자열이 어떤 언어의 구성원인지 식별하는 문제이다.
더욱 구체적으로 말하면 해석은 기호 목록을 더욱 높은 차원 구조를 나타내는 데이터 구조로 바꾸는 임무이다.해석된 경우 기호 세트 입력은 문자†입니다.
전통적으로 프로그래밍 언어의 해석은 두 단계로 나뉘는데 그것이 바로 어법 분석 단계와 해석 단계이다.사실상 이 두 단계는 모두 해석기이다. 그들은 모두 기호의 입력 목록을 받아들이고 더욱 높은 수준의 구조를 생성한다.단지 lexer의 출력은 해상도 입력으로 사용됩니다.
이 분리는 해상도보다 간단하기 때문에 유용합니다. lexer는 무의미한 문자열을 숫자 문자, 문자열 문자, 표지부 또는 연산자 같은 간단한 목록으로 변환하고 보존 표지부 (키워드) 를 식별하고 공백을 버릴 수 있습니다.형식적으로 말하자면lexer는 Regular languages을 식별한다.'일반'언어는 하나의 비거슬러 올라가는 과정에서 어떠한 추가 상태도 필요 없이 해석할 수 있는 언어이다.이것은 매우 효율적이다. 당신은 매번 한 바이트만 보면 결정을 내릴 수 있고, 모든 결정을 Finite Automaton이라는 결정 행렬로 포장할 수 있다.정규 표현식을 사용한 적이 있다면, 정규 언어를 위한 식별기를 작성했습니다.
해상도 작업이 훨씬 어려워서lexer가 생성한'영패'유류를 해상도 언어 구조를 나타내는 해상도 트리로 변환합니다.lexer와 해상도의 분리로 인해 lexer는 작업을 잘 완성할 수 있고 해상도는 원시 텍스트보다 더 간단하고 의미 있는 입력을 처리할 수 있다.
비록 많은 방법이lexer를 생성할 수 있지만, 우리는 그것의 구조를 볼 수 있도록 수동으로 lexer를 실현할 것이다.lexer의 가장 간단한 형식은
fn(&str) -> Token인데 그 중에서 Token은 (Kind, Length)쌍이다.이것이 바로 우리가 실현하고자 하는 API이지만, 편의를 위해 fn(&str) -> impl Iterator<Item=Token> 액세스 포인트를 제공하였다.이것은 절대적으로 정확한 변환입니다. 의외의 문자에 대해서는 오류 표시만 되돌려줍니다.Lexer가 무엇을 인식해야 하는지 확인하기 위해 Tiny-C 문법을 다시 한 번 살펴보겠습니다.
Program = Statement;
Statement =
| If:{ "if" cond:ParenExpr then:Statement else:{ "else" then:Statement } }
| While:{ "while" cond:ParenExpr then:Statement }
| Block:{ "{" then:Statement* "}" }
| Expr:{ then:Statement? ";" }
;
ParenExpr = "(" Expr ")";
Expr =
| Assign:{ id:Id "=" val:Expr }
| Test:{ lhs:Expr "<" rhs:Expr }
| Sum:{ lhs:Expr "+" rhs:Term }
| Diff:{ lhs:Expr "-" rhs:Term }
;
Term =
| Id:{ 'a'..='z'+ }
| Int:{ '0'..='9'+ }
| Expr:ParenExpr
;
if, else과 while이 있습니다.표점 {/}, ;, (/), =, <, +, -과 Id;그리고 Int(하나 이상의 소문자 ascii 문자)과 tinyc_grammar(하나 이상의 ascii 숫자)의 단말기 곱셈.이제 우리는 무엇을 실현해야 할지 알게 되었다. 우리는 어떻게 우리의 작업 구역을 구축할 것인지를 결정해야 한다.전형적인 개발에 대해 나는 IntelliJ IDEA과 IntelliJ Rust을 사용한다.단, 본 시리즈에 대해 저는 환경이 Visual Studio Code과 rust-analyzer이라고 가정할 것입니다. 왜냐하면 VSCode는 언어 서버 개발에 사용되기 때문입니다.규범 환매는 https://github.com/cad97/tinyc에 있다.
우리는 모듈화된 컴파일러를 구축하고 싶기 때문에, 물건을 서로 다른 판자 상자로 나누고 싶다.따라서 새 디렉터리에 virtual manifest을 설정하고 우리의 첫 번째 판자 상자
cargo-edit을 만듭니다.문법 패널 상자는 우리의 문법 유형에 대한 정의를 포함하고 거의 완전히 메타데이터로 생성될 것이다.우리는 현재 단말기 영패 유형만 설정할 준비가 되어 있지만, 이것은 후속 작업을 위한 틀을 세울 것이다.우리가 필요로 하는 구축 의존 항목( [email protected] 관리 사용):cargo add -sB glob heck serde tera toml --allow-prerelease
[email protected], [email protected], [email protected], [email protected]과 serde을 얻어냈다."derive"의 syntax.toml 기능을 사용해야 합니다.언어에 대한 메타데이터를 저장할 폴더가 필요합니다.그 중에서 우리는
syntax_kinds.rs을 만들었다.# The keywords of our language.
keywords = [
"else",
"if",
"while",
]
# Literal data embedded in the source.
literals = [
"integer",
]
# Symbols alongside names for them.
punctuation = [
['{', "left curly bracket"],
['}', "right curly bracket"],
['(', "left parenthesis"],
[')', "right parenthesis"],
['+', "plus sign"],
['-', "hyphen minus"],
['<', "less than sign"],
[';', "semicolon"],
['=', "equals sign"],
]
# Tokens that don't fall into one of the above categories.
# "error" is for errors: when we encounter something unexpected.
# "whitespace" is the white space between tokens, and is explicit in our lexer.
tokens = [
"error",
"identifier",
"whitespace",
]
{% %}을 일일이 열거하여 Tera 템플릿을 만들어야 한다.// This is just a workaround: for some reason
// a tera filter expression cannot start with a literal empty array
{%- set empty = [] -%}
// Create a variable for accessing every kind
// by concatenating each individual kind
{%- set all_kinds = empty
| concat(with=keywords)
| concat(with=literals)
| concat(with=punctuation | map(attribute="name"))
| concat(with=tokens)
-%}
// Rowan internally stores kind as a u16
#[repr(u16)]
// We won't be generating docs
#[allow(missing_docs)]
// Derive all of the standard traits we can
#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub enum SyntaxKind {
{%- for kind in all_kinds %}
// list each kind in camel_case
{{ kind | camel_case }},
{%- endfor %}
}
set all_kinds은 제어 문장이다.맨 위에 kind in all_kinds은 목록을 여러 번 사용할 수 있도록 다양한 종류의 그룹을 정의했습니다.매거 정의에서 우리는 각 {{ }}을 교체하고 camel_case을 사용하여 grammar의 모든 유형으로 변환합니다.현재 우리는 이미 메타데이터를 설치했는데, 실제로는
build.rs 판자 상자를 생성할 수 있다!include!을 만들고 다음을 추가합니다.use {
glob::glob,
heck::*,
serde::{Deserialize, Serialize},
std::{
collections::HashMap,
env,
error::Error,
fs,
path::{Path, PathBuf},
},
tera::{self, Context, Tera, Value},
toml,
};
/// The manifest directory.
const MANIFEST: &str = env!("CARGO_MANIFEST_DIR");
/// Project-relative path to the syntax metadata.
const SYNTAX_CONFIG: &str = "meta/syntax.toml";
/// Directory containing the Tera templates.
const TEMPLATE_DIR: &str = "meta";
/// The sytnax kinds enum template.
pub const SYNTAX_KINDS: &str = "syntax_kinds.rs";
/// Easy access to the project root path.
fn project_root() -> &'static Path {
// We take the 2nd ancestor as our crate's manifest is two folders deep.
Path::new(MANIFEST).ancestors().nth(2).unwrap()
}
/// The structured syntax metadata.
///
/// We derive Serialize to serialize to a Tera config object
/// and Deserialize to deserialize from the metadata file.
#[derive(Serialize, Deserialize)]
struct SyntaxConfig {
keywords: Vec<String>,
literals: Vec<String>,
punctuation: Vec<PunctuationConfig>,
tokens: Vec<String>,
}
/// A punctuation config item, represented in toml as `["character", "name"]`.
///
/// We derive Serialize so the Tera config object has named members,
/// but implement Deserialize manually to deserialize from an unnamed sequence.
///
/// Note that this means `de::from_str(ser::to_string(punctuation_config))`
/// does not work, as the two formats do not line up. This is only ok to do
/// here because these are the _only_ de/serialization tasks we care about.
#[derive(Serialize)]
struct PunctuationConfig {
character: char,
name: String,
}
impl<'de> Deserialize<'de> for PunctuationConfig {
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: serde::de::Deserializer<'de>,
{
#[derive(Deserialize)]
#[serde(rename = "PunctuationConfig")]
struct Helper(char, String);
// We implement deserialize by just delegating to a helper tuple struct type.
Helper::deserialize(deserializer).map(|helper| PunctuationConfig {
character: helper.0,
name: helper.1,
})
}
}
/// A helper function to make Tera filter functions `(value, keys) -> Value`
/// out of a simpler `(T) -> T` transformation.
fn make_filter_fn<'a, T: Into<Value> + serde::de::DeserializeOwned>(
name: &'a str,
f: impl Fn(T) -> T + Sync + Send + 'a,
) -> impl tera::Filter + 'a {
move |value: &Value, _: &HashMap<String, Value>| -> tera::Result<Value> {
let val = tera::try_get_value!(name, "value", T, value);
Ok(f(val).into())
}
}
fn main() -> Result<(), Box<dyn Error>> {
let root = project_root();
let templates = root.join(TEMPLATE_DIR).join("**/*.rs");
let syntax_config = root.join(SYNTAX_CONFIG);
// All generated files go into `$OUT_DIR` and are `include!`d from there.
let out = PathBuf::from(env::var("OUT_DIR")?);
// We have to tell cargo we depend on these files
// so that cargo will rerun the build script when the files change.
println!("cargo:rerun-if-changed={}", syntax_config.to_string_lossy());
for path in glob(&templates.to_string_lossy())? {
println!("cargo:rerun-if-changed={}", path?.to_string_lossy());
}
let tera = {
// Initialize Tera.
let mut tera = Tera::new(&root.join(templates).to_string_lossy())?;
// Add the `camel_case` filter using `heck`.
tera.register_filter(
"camel_case",
make_filter_fn("camel_case", |s: String| s.to_camel_case()),
);
tera
};
// Read in the context file.
let config: SyntaxConfig = toml::from_str(&fs::read_to_string(syntax_config)?)?;
// And convert it into the Tera-compatible form.
let context = Context::from_serialize(config)?;
// Write out the generated file.
fs::write(
out.join(SYNTAX_KINDS),
tera.render(SYNTAX_KINDS, context.clone())?,
)?;
Ok(())
}
lib.rs에서 생성된 파일만 있으면 됩니다.include!(concat!(env!("OUT_DIR"), "/syntax_kinds.rs"));
grammar 판자 상자가 시작되고 실행되었습니다!이 점에서 너는 cargo doc을 해서 우리의 현재 진전을 볼 수 있다.다음 단계는 실제적으로lexer를 작성하는 것이다. 이렇게 하면 우리는 실제적으로 뭔가를 실행할 수 있다.그럼, 우리 lexer를 만듭시다!
cargo new --lib crates/lexer --name tinyc_lexer
cd crates/lexer
cargo add ../grammar
code src/lib.rs
use std::u32;
// Re-export for ease of use.
pub use grammar::SyntaxKind;
/// A single token in the document stream.
#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub struct Token {
/// The kind of token.
pub kind: SyntaxKind,
/// How many bytes this token is.
pub len: u32,
}
/// Convenience function for repeatedly applying `lex`.
pub fn tokenize(mut source: &str) -> impl Iterator<Item = Token> + '_ {
// Our compiler tooling assumes source files < 4 GiB in size.
assert!(source.len() < u32::MAX as usize);
std::iter::from_fn(move || {
if source.is_empty() {
return None;
}
let token = lex(source);
source = &source[token.len as usize..];
Some(token)
})
}
/// Lex the first token off of the source string.
pub fn lex(source: &str) -> Token {
debug_assert!(!source.is_empty());
debug_assert!(source.len() < u32::MAX as usize);
// Classify the token.
if source.starts_with(is_whitespace) {
// Whitespace token.
Token {
kind: SyntaxKind::Whitespace,
len: source.find(is_not_whitespace).unwrap_or(source.len()) as u32,
}
} else if source.starts_with(is_digit) {
// Integer token.
Token {
kind: SyntaxKind::Integer,
len: source.find(is_not_digit).unwrap_or(source.len()) as u32,
}
} else if source.starts_with(is_ident) {
// Identifier token.
let len = source.find(is_not_ident).unwrap_or(source.len());
Token {
// This is a new function on `SyntaxKind` we'll add next.
kind: SyntaxKind::from_identifier(&source[..len]),
len: len as u32,
}
} else {
// Punctuation token.
let ch = source.chars().next().unwrap();
Token {
kind: match ch {
'{' => SyntaxKind::LeftCurlyBracket,
'}' => SyntaxKind::RightCurlyBracket,
'(' => SyntaxKind::LeftParenthesis,
')' => SyntaxKind::RightParenthesis,
'+' => SyntaxKind::PlusSign,
'-' => SyntaxKind::HyphenMinus,
'<' => SyntaxKind::LessThanSign,
';' => SyntaxKind::Semicolon,
'=' => SyntaxKind::EqualsSign,
// Unknown tokens are an error.
_ => SyntaxKind::Error,
},
len: ch.len_utf8() as u32,
}
}
}
// Helper functions for classifying characters.
fn is_whitespace(c: char) -> bool {
c.is_whitespace()
}
fn is_not_whitespace(c: char) -> bool {
!is_whitespace(c)
}
fn is_digit(c: char) -> bool {
c.is_ascii_digit()
}
fn is_not_digit(c: char) -> bool {
!is_digit(c)
}
fn is_ident(c: char) -> bool {
'a' <= c && c <= 'z'
}
fn is_not_ident(c: char) -> bool {
!is_ident(c)
}
syntax_kinds.rs에 몇 가지 새로운 함수를 추가해야 합니다.impl SyntaxKind {
/// The syntax kind for a keyword.
pub fn from_keyword(ident: &str) -> Option<SyntaxKind> {
match ident {
{% for keyword in keywords -%}
"{{ keyword }}" => Some(SyntaxKind::{{ keyword | camel_case }}),
{% endfor -%}
_ => None,
}
}
/// The syntax kind for an identifer.
///
/// Note that this doesn't do any validation of the identifier,
/// it just uses whatever you give it.
pub fn from_identifier(ident: &str) -> SyntaxKind {
SyntaxKind::from_keyword(ident).unwrap_or(SyntaxKind::Identifier)
}
}
cargo doc을 사용하여 lexer의 API를 다시 봅니다.그러나lexer의 작업 원리를 진정으로 증명하기 위해서는 테스트를 작성해야 한다.편의를 위해서 우리는 conformance::tests 테스트 라이브러리를 사용할 것이다.따라서
conformance과 serde_yaml을 개발 의존항으로 우리의 lexer 패널 상자에 추가하고 새로운 테스트 파일을 만듭니다.cargo add -sD conformance serde_yaml
code ./tests/conformance.rs
use {
conformance, serde_yaml,
tinyc_lexer::{tokenize, Token},
};
#[conformance::tests(exact, serde=serde_yaml, file="tests/main.yaml.test")]
fn lex_tokens(s: &str) -> Vec<Token> {
tokenize(s).collect()
}
code ./tests/main.yaml.test
1
===
a=b=c=2<3;
---
[] # empty tests for now
...
2
===
{ i=1; while (i<100) i=i+i; }
---
[]
...
3
===
{ i=125; j=100; while (i-j) if (i<j) j=j-i; else i=i-j; }
---
[]
...
4
===
{ i=1; do i=i+10; while (i<50); }
---
[]
...
5
===
{ i=1; while ((i=i+10)<50) ; }
---
[]
...
6
===
{ i=7; if (i<5) x=1; if (i<10) y=2; }
---
[]
...
error[E0277]: the trait bound `tinyc_lexer::Token: serde::ser::Serialize` is not satisfied
--> crates\lexer\tests\conformance.rs:6:1
|
6 | #[conformance::tests(exact, serde=serde_yaml, file="tests/main.yaml.test")]
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `serde::ser::Serialize` is not implemented for `tinyc_lexer::Token`
|
::: D:\usr\.cargo\registry\src\github.com-1ecc6299db9ec823\serde_yaml-0.8.11\src\ser.rs:421:8
|
421 | T: ser::Serialize,
| -------------- required by this bound in `serde_yaml::ser::to_string`
|
= note: required because of the requirements on the impl of `serde::ser::Serialize` for `std::vec::Vec<tinyc_lexer::Token>`
Serialize의 실현은 우리가 예상한 수출과 실제 생산을 비교하는 데 사용한 것이다.따라서 syntax_kinds.rs 템플릿에 새로운 조수를 추가했습니다.impl SyntaxKind {
/// The name of this syntax kind.
pub const fn name(self) -> &'static str {
match self {
{% for kind in all_kinds -%}
SyntaxKind::{{ kind | camel_case }} => "{{ kind | camel_case }}",
{% endfor -%}
#[allow(unreachable_patterns)]
_ => "", // For the future
}
}
}
tinyc_lexer::Token에 대해 우리는 수동으로 Serialize을 실현한다.왜?만약 우리가 그것을 바꾸지 않는다면 (Token: length) 기본 서열화보다 더 좋은 서열화를 얻을 수 있기 때문이다.cargo add -s serde
code src/serde.rs
use {
super::*,
serde::ser::{Serialize, Serializer},
};
impl Serialize for Token {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
serializer.serialize_newtype_variant(
// The name of the type
"Token",
// TokenKind is `#[repr(u16)]`, so this cast is legal
self.kind as u16 as u32,
// Using our added helper to get the name of the kind
self.kind.name(),
// The data payload of the serialized newtype variant
&self.len,
)
}
}
{ kind: "Token", len: length }을 서열화했는데 마치 Token과 같다. 이것이 바로 그의 진정한 행위이다.우리는 단지 그것을 enum Token { Kind(u32) } 모듈로 분리할 뿐이다. 왜냐하면 길이가 없는 모듈을 생성하고 조작하는 것은 컴파일러에 매우 유용하기 때문이다.((kind, length)이 포함된 파일을 잊지 마십시오.)테스트를 실행하면 테스트는 컴파일되지만 실패합니다. 예시가 영패의 빈 서열로 분해될 것이라고 단언하기 때문입니다.불행하게도 IntelliJ Rust와 같은 IDE 통합이 없다면 기본
mod serde이 제공하는 차이는 이런 빅데이터에 있어서 정말 읽기 어렵다.---- main_yaml_1 stdout ----
thread 'main_yaml_1' panicked at 'assertion failed: `(left == right)`
left: `"---\n- Identifier: 1\n- EqualsSign: 1\n- Identifier: 1\n- EqualsSign: 1\n- Identifier: 1\n- EqualsSign: 1\n- Integer: 1\n- LessThanSign: 1\n- Integer: 1\n- Semicolon: 1"`,
right: `"---\n[]"`', crates\lexer\tests\conformance.rs:6:1
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.
그러나 unescape tool과 diff tool은 수출에 의미가 있다.생성된 출력이 예상에 부합되는지 확인한 다음 테스트 파일에 복사하여 미래에 변화가 있는지 확인하십시오.
그것 이 있으면 우리 는 일할 수 있는 lexer 가 생겼다!다음에 우리는 첫 번째 단계를 취해 영패를 문법 트리로 해석할 것이다.
Discuss this below! | See the result on GitHub!
→ 인물은 거짓말이다.반대로 우리가 연구한 것은 유니코드 Abstract Characters나 코드 점이다.이것은 Rust의
assert_eq! 데이터 유형에 대한 32비트 값입니다.불행하게도 인류가 감지하는 역할은 모호한 개념으로 인류 언어 사이에 심지어 일치하지 않는다.유니코드는 (Extended) Grapheme Cluster의 개념을 가지고 있는데 대체적으로 이 개념에 접근하려고 하지만 이것은 우리의 수요를 초과하는 자신의 해석기가 필요하다.코드 포인트를 연구하면 충분하다.어쨌든 문자열을 제외한 대부분의 프로그래밍 언어는 ASCII 이외의 어떤 것도 허용하지 않는다.‡ 일부 정규 표현식 엔진은 정규 표현식 언어에 대해 비정규 확장을 허용한다.정규 표현식은 매우 편리하고 정규 해석 기술을 사용하는 데 한계가 있기 때문에 역방향 인용 등 기능을 도입하여 유한한 형식의 상하문 민감한 해석을 실현해야 한다.일부 엔진, 예를 들어 Rust의 regex crate은 이러한 비규칙적인 특성을 실현하지 못해'정칙 표현식 성능 함정'을 완전히 없앨 수 있다.
관련 읽기
스택 넘침 lexers vs parsers
Reference
이 문제에 관하여(Lexer란 무엇입니까?), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/cad97/what-is-a-lexer-anyway-4kdo텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
