मनोरंजन और लाभ के लिए WebAssembly भाषा कैसे बनाएं: पार्सिंग

में अंतिम पोस्ट WebAssembly प्रोग्रामिंग भाषा बनाने के तरीके पर इस श्रृंखला में, हमने एक लेक्सर का निर्माण किया। इस पोस्ट में, हम अपने कंपाइलर, पार्सिंग के अगले चरण को कवर करेंगे। पार्सिंग हमारे कंपाइलर का वह हिस्सा है जो लेक्सर द्वारा उत्पन्न टोकन स्ट्रीम लेता है और इसे एक में परिवर्तित करता है सार वाक्य रचना वृक्ष (एएसटी)।

एएसटी एक पेड़ जैसी डेटा संरचना है जो टोकन को एक तार्किक पदानुक्रम में व्यवस्थित करती है जिसे मशीन कोड में अधिक आसानी से अनुवादित किया जा सकता है। शुक्र है, क्योंकि wispy एक S-अभिव्यक्ति भाषा है, हमारा कोड अनिवार्य रूप से पहले से ही एक AST है। टोकन की निम्नलिखित धारा लें:

 “(“, “add”, “3”, “(“, “sub”, “2”, “1”, “)”, “)”

कोष्ठक का प्रत्येक सेट एक उपट्री का प्रतिनिधित्व करता है, जहां पहला टोकन ऑपरेटर नोड होता है और निम्नलिखित टोकन इसके ऑपरेंड होते हैं। यदि हम वर्तमान सेट बंद होने से पहले एक और उद्घाटन कोष्ठक में चलते हैं, तो हम जानते हैं कि यह एक ऑपरेंड का प्रतिनिधित्व करता है जो स्वयं एक उपट्री है। टोकन की उपरोक्त धारा को इस तरह दिखने वाले पेड़ में व्यवस्थित किया जाएगा:

यदि आप अधिक जटिल सी-जैसे सिंटैक्स के लिए एक पार्सर लिखने में रुचि रखते हैं, तो मेरा पिछला देखें एक प्रोग्रामिंग भाषा का निर्माण श्रृंखला।

एएसटी . के बारे में अधिक

जैसा कि हमने लेक्सर के साथ किया था, हम अपने प्रकारों को परिभाषित करके शुरू करेंगे। ये प्रकार हमारे एएसटी की संरचना को परिभाषित करेंगे। प्रत्येक प्रकार एक "नोड" का प्रतिनिधित्व करता है, परिचय में हमारे आरेख से सर्कल। यहाँ बुनियादी नोड्स हैं। हम उन पर प्रकाश डालेंगे, क्योंकि वे हमारे द्वारा लेक्सर में परिभाषित टोकन से बहुत अलग नहीं हैं:

 // src/types/ast.mts export type IntNode = { type: "int"; value: number; }; export type FloatNode = { type: "float"; value: number; }; export type IdentifierNode = { type: "identifier"; identifier: string; }; export type TypedIdentifierNode = { type: "typed-identifier"; // Note that here, we break down the identifier into its components identifier: string; typeIdentifier: string; };

AST की एक नई अवधारणा BlockNode है। एक BlockNode अन्य नोड्स के समूह से बना एक अभिव्यक्ति है।

उदाहरण के लिए, (add 1 2) तीन नोड्स का एक ब्लॉक है:

1. एक पहचानकर्ता जो किसी फ़ंक्शन का मूल्यांकन करता है, add ।
2. एक इंट जो केवल संख्या 1 का मूल्यांकन करता है।
3. एक इंट जो केवल संख्या 2 का मूल्यांकन करता है।

ब्लॉक का मूल्यांकन कैसे किया जाता है यह संकलक पर निर्भर करता है। हम इसे अगले पोस्ट में प्राप्त करेंगे।

यहाँ परिभाषा है:

 // src/types/ast.mts export type BlockNode = { type: "block"; expressions: AstNode[]; };

अंत में, हम AstNode को परिभाषित करते हैं। लेक्सर से Token प्रकार की तरह, AstNode एक भेदभावपूर्ण संघ है जो किसी भी अन्य नोड में से एक हो सकता है जिसे हमने पहले परिभाषित किया था:

 export type AstNode = IntNode | FloatNode | IdentifierNode | TypedIdentifierNode | BlockNode;

आपने देखा होगा कि BlockNode में AstNode s की एक सरणी होती है, क्योंकि AstNode एक BlockNode हो सकता है, BlockNode s में चाइल्ड BlockNodes हो सकता है। दूसरे शब्दों में, BlockNode एक पुनरावर्ती प्रकार है। बच्चों को पुन: प्रस्तुत करने की यह क्षमता हमारे एएसटी की नींव है। यह वह जगह है जहां एएसटी में पेड़ बनने की इजाजत है।

इस बिंदु पर src/types/ast.mts समाप्त हो गया है और ऐसा दिखना चाहिए यह फ़ाइल .

अब src/types/index.mts से प्रकारों को निर्यात करें जैसा कि हमने टोकन प्रकारों के साथ किया था:

 // src/types/index.mts export * from "./token.mjs"; export * from "./ast.mjs";

एएसटी . का निर्माण

अब जब हमने एएसटी को परिभाषित कर दिया है, तो इसे बनाने का समय आ गया है।

एक नई src/parser.mts फ़ाइल बनाएँ और उन सभी आयातों को जोड़ें जिनका हम उपयोग करेंगे:

 // src/parser.mts import { Token, IdentifierNode, TypedIdentifierNode, IdentifierToken, TypedIdentifierToken, FloatToken, FloatNode, IntToken, IntNode, AstNode, BlockNode, } from "./types/index.mjs";

अब हम अपने शीर्ष स्तरीय पार्स फ़ंक्शन को परिभाषित कर सकते हैं। पार्स फ़ंक्शन लेक्सर द्वारा उत्पन्न टोकन लेता है और एक BlockNode देता है जो हमारे पेड़ की जड़ के रूप में कार्य करता है।

 // src/parser.mts export const parse = (tokens: Token[]): BlockNode => { const blocks: BlockNode[] = []; // This loop is run as long as there are tokens to consume while (tokens.length) { // consumeTokenTree converts an array of tokens into a tree of tokens, more on that later. const tree = consumeTokenTree(tokens); // parseBlock turns our new tree of tokens into an actual BlockNode, recursively. More on that later as well. blocks.push(parseBlock(tree)); } // Finally we return the top level BlockNode return { type: "block", expressions: blocks, }; };

अगला, हम consumeTokenTree फ़ंक्शन को परिभाषित करते हैं। consumeTokenTree टोकन के एक फ्लैट सरणी को टोकन के पेड़ में परिवर्तित करता है।

इस बुद्धिमान अभिव्यक्ति को देखते हुए:

 (add (sub 3 1) (sub 5 2))

लेक्सर टोकन की इस सरणी का उत्पादन करेगा:

 // Note: I've simplified the Token format to just be strings to keep things short ["(", "add", "(", "sub", "3", "1", ")", "(", "sub", "5", "2", ")", ")"];

consumeTokenTree उस सपाट सरणी को लेगा और उसे एक पेड़ में बदल देगा। यह हर टोकन को ब्रैकेट टोकन () के एक सेट के बीच एक सरणी में डालने जितना आसान है। तो ऊपर से हमारा टोकन ऐरे यह टोकन ट्री बन जाता है:

 ["add", [, "sub", "3", "1"], ["sub", "5", "2"]];

यहाँ consumeTokenTree की वास्तविक परिभाषा है:

 // src/parser.mts // This is token besides for the bracket tokens export type NonBracketToken = Exclude<Token, "parenthesis" | "square-bracket">; // The token tree is made of NonBracketTokens and other TokenTrees export type TokenTree = (NonBracketToken | TokenTree)[]; const consumeTokenTree = (tokens: Token[]): TokenTree => { const tree: TokenTree = []; // Ensures the first token is a left bracket and then discards it, defined below this function. consumeLeftBracket(tokens); while (tokens.length) { // Preview the next token const token = tokens[0]; // Check to see if the next token is a left bracket. if (token.type === "bracket" && getBracketDirection(token) === "left") { // If it is, we just ran into a sub-TokenTree. So we can simply call this function within // itself. Gotta love recursion. tree.push(consumeTokenTree(tokens)); continue; } // Check to see if the next token is a right bracket if (token.type === "bracket" && getBracketDirection(token) === "right") { // If it is, we just found the end of the tree on our current level tree.shift(); // Discard the right bracket break; // Break the loop } // If the token isn't a bracket, it can simply be added to the tree on this level tree.push(token); // Consume / discard the token from the main tokens array tokens.shift(); } // Return the tree. Don't forget to check out the helper functions below! return tree; }; const consumeLeftBracket = (tokens: Token[]) => { const bracketDirection = getBracketDirection(tokens[0]); if (bracketDirection !== "left") { throw new Error("Expected left bracket"); } return tokens.shift(); }; const getBracketDirection = (token: Token): "left" | "right" => { if (token.type !== "bracket") { throw new Error(`Expected bracket, got ${token.type}`); } // If we match a left bracket return left if (/[\(\[]/.test(token.value)) return "left"; // Otherwise return right return "right"; };

अब जब हमारे पास एक टोकन ट्री है, तो हमें इसे एक ब्लॉक में बदलना होगा। ऐसा करने के लिए, हम एक parseBlock फ़ंक्शन बनाते हैं जो पेड़ को इसके इनपुट के रूप में लेता है और एक BlockNode देता है:

 1const parseBlock = (block?: TokenTree): BlockNode => { return { type: "block", // This is where the recursive magic happens expressions: block.map(parseExpression), }; };

जैसा कि आपने देखा होगा, parseBlock पेड़ के प्रत्येक आइटम को अभी तक लिखे parseExpression फ़ंक्शन के साथ मैप करता है। parseExpression या तो एक TokenTree या एक NonBracketToken लेता है और इसे इसके संबंधित AstNode प्रकार में बदल देता है।

यहाँ परिभाषा है:

 const parseExpression = (expression?: TokenTree | NonBracketToken): AstNode => { // If the expression is an Array, we were passed another TokenTree, so we can // pass the expression back to the parseBlock function if (expression instanceof Array) { return parseBlock(expression); } // The mapping here is pretty straight forward. Match the token type and pass the // expression on to a more specific expression parser. if (isTokenType(expression, "identifier")) return parseIdentifier(expression); if (isTokenType(expression, "typed-identifier")) return parseTypedIdentifier(expression); if (isTokenType(expression, "float")) return parseFloatToken(expression); if (isTokenType(expression, "int")) return parseIntToken(expression); throw new Error(`Unrecognized expression ${JSON.stringify(expression)}`); };

आइए isTokenType फ़ंक्शन को परिभाषित करें। यह फ़ंक्शन बहुत साफ-सुथरा है और टाइपस्क्रिप्ट की सबसे शक्तिशाली विशेषताओं में से एक को प्रदर्शित करता है, कस्टम प्रकार के गार्ड . सीधे शब्दों में कहें, isTokenType अभिव्यक्ति का परीक्षण करता है और प्रकार को एक विशिष्ट TokenType तक सीमित करता है। यह टाइपस्क्रिप्ट को यह सुनिश्चित करने की अनुमति देता है कि हम लाइन के नीचे उनके संबंधित पार्सर कार्यों के लिए सही टोकन पास कर रहे हैं।

यहाँ परिभाषा है:

 export const isTokenType = <T extends Token["type"]>( item: TokenTree | NonBracketToken | undefined, type: T ): item is Extract<Token, { type: T }> => { return isToken(item) && item.type === type; }; const isToken = (item?: TokenTree | NonBracketToken): item is NonBracketToken => { return !(item instanceof Array); };

वहाँ बहुत कुछ हो रहा है, तो चलिए इसके माध्यम से चलते हैं। सबसे पहले, हमारे पास एक सामान्य परिभाषा है, <T extends Token["type"]> । यह अनिवार्य रूप से कह रहा है कि T को Token.type फ़ील्ड के संभावित मानों में से एक होना चाहिए। टाइपस्क्रिप्ट यह जानने के लिए काफी स्मार्ट है कि T को "int" | "float" | "identifier" | "typed-identifier" | "bracket ।

कोड का अगला दिलचस्प टुकड़ा रिटर्न टाइप विधेय item is Extract<Token, { type: T }> । यह विधेय टाइपस्क्रिप्ट को बताता है कि यदि isTokenType का रिटर्न मान सत्य है, तो item को Token होना चाहिए जिसका प्रकार type पैरामीटर के रूप में पारित स्ट्रिंग से मेल खाता हो।

व्यवहार में इसका मतलब है कि अगर हम एक अज्ञात Token को isTokenType पर पास करते हैं, तो टाइपस्क्रिप्ट मान को अधिक विशिष्ट टोकन, जैसे IntToken तक सही ढंग से सीमित करने में सक्षम होगा।

अब जब हमारे पास अपना कस्टम प्रकार गार्ड परिभाषित है, तो हम वास्तविक टोकन पार्सर्स को परिभाषित कर सकते हैं। पहले तीन सरल हैं; वे अनिवार्य रूप से टोकन की एक प्रति या थोड़ी संशोधित प्रति लौटाते हैं:

 const parseFloatToken = (float: FloatToken): FloatNode => ({ ...float }); const parseIntToken = (int: IntToken): IntNode => ({ ...int }); const parseIdentifier = (identifier: IdentifierToken): IdentifierNode => { return { type: "identifier", identifier: identifier.value, }; };

अंतिम पार्सर parseTypedIdentifier है। याद रखें कि टाइप किया गया पहचानकर्ता प्रपत्र identifier:type लेता है। इसे पार्स करना उतना ही सरल है जितना कि कोलन द्वारा स्ट्रिंग को विभाजित करना। लौटाए गए सरणी का पहला मान identifier है, दूसरा type है। यहाँ परिभाषा है:

 const parseTypedIdentifier = (identifier: TypedIdentifierToken): TypedIdentifierNode => { const vals = identifier.value.split(":"); return { type: "typed-identifier", identifier: vals[0], typeIdentifier: vals[1], }; };

यहाँ समाप्त फ़ाइल है

एक कार्यशील पार्सर के लिए आवश्यक सभी कोड हैं। आगे बढ़ने से पहले, आइए पार्सर के आउटपुट को देखने के लिए मुख्य src/index.mts फ़ाइल को अपडेट करें:

 // src/index.mts #!/usr/bin/env node import { readFileSync } from "fs"; import { lex } from "./lexer.mjs"; import { parse } from "./parser.mjs"; const file = process.argv[2]; const input = readFileSync(file, "utf8"); const tokens = lex(input); const ast = parse(tokens); console.log(JSON.stringify(tokens, undefined, 2));

प्रोजेक्ट बनाएं और चलाएं:

 npx tsc wispy example.wispy

अगर सब ठीक हो जाता है, तो आउटपुट दिखना चाहिए यह .

उसके साथ, पार्सर समाप्त हो गया है। अब हम लेक्सर से टोकन की धारा को एएसटी में बदल सकते हैं। अगली पोस्ट में, हम रसदार बिट्स में आ सकते हैं: मशीन-पठनीय कोड बनाना और चलाना।

उत्पाद सूचनाओं को आनंदमय बनाने के लिए कूरियर कैसे काम करता है, यह देखने के लिए आज ही डेमो का अनुरोध करें!