چگونه یک مترجم ساده در جاوا اسکریپت بنویسیم

مقدمه ای بر فرآیند کامپایل/تفسیر با ساخت یک برنامه ماشین حساب ساده در جاوا اسکریپت

دانلود کد های این مقاله:

نوشتن مفسرها و کامپایلرهای

نوشتن مفسر یا کامپایلر یکی از آموزشی ترین کارها در برنامه نویسی است زیرا می توانید با جزئیات فرآیند تفسیر و ارزیابی کد آشنا شوید. شما می توانید دانش بسیار عمیق تری از انواع چیزهایی که در پشت صحنه می گذرد به دست آورید و بینش هایی در مورد تصمیمات پشت طراحی زبان به دست آورید.

این مقاله با نشان دادن نحوه نوشتن یک مفسر برای یک زبان ساده که می توانیم برای یک برنامه ماشین حساب از آن استفاده کنیم، یک نمای کلی از این فرآیند را انجام می دهد.

این مقاله فرض می کند که شما تجربه برنامه نویسی متوسط ​​و آشنایی اولیه با جاوا اسکریپت دارید.

برخی از پس زمینه

تفاوت بین مترجمان، کامپایلرها و ترانسپایلرها

در این مقاله، بر خلاف کامپایلر ، یک مفسر ایجاد خواهیم کرد. برنامه ما مقداری کد را به عنوان ورودی می گیرد و بلافاصله آن را اجرا می کند.

اگر ما یک کامپایلر می‌نوشتیم، در عوض کدهای وارد شده در زبان مبدأ را به کدهایی در برخی از زبان‌های هدف سطح پایین‌تر مانند MSIL یا یک زبان اسمبلی یا حتی کد ماشین تبدیل می‌کردیم.

ترانسپایلر شبیه کامپایلر است، با این تفاوت که زبان مبدأ و زبان مقصد تقریباً در یک سطح از انتزاع هستند. مثال متعارف آن در دنیای برنامه نویسی وب سمت مشتری، CoffeeScript است که به جاوا اسکریپت تبدیل می شود.

فرآیند تفسیر کد زبان سنتی

اکثر کامپایلرها کد را در یک فرآیند چند مرحله ای تفسیر می کنند که شامل فرآیندهایی می شود که شامل تحلیل واژگانی ، پیش پردازش ، تجزیه ، بهینه سازی و در نهایت تولید کد ، یا در مورد مفسر، ارزیابی است.

در این مقاله، ما فقط بر روی واژه نویسی، تجزیه و تحلیل و ارزیابی تمرکز خواهیم کرد.

لکسینگ

یک lexer یک ورودی رشته ای از کاراکترها را می گیرد و لیستی از نشانه ها را خروجی می کند. به عنوان مثال، اگر کدی مانند این داشتیم …

(۱۲ + ۴) / ۶

… lexer آن را به بخش‌های مجزا تقسیم می‌کند که توکن نامیده می‌شوند و فهرستی شبیه به این تولید می‌کند.

[
  ["operator", "("],
  ["number", 12],
  ["operator", "+"],
  ["number", 4],
  ["operator", ")"],
  ["operator", "/"],
  ["number", 6]
]

این فرآیند معمولاً نسبتاً ساده است. شخصی با کمی تجربه در دستکاری رشته می تواند راه خود را از طریق ساخت lexer نسبتاً سریع انجام دهد.

تجزیه

تجزیه کننده لیستی از نشانه های تولید شده توسط lexer را به عنوان ورودی می گیرد، آن را بر اساس برخی از قوانین نحوی تجزیه می کند و نمایشی از ساختار نحوی به نام درخت تجزیه را خروجی می دهد.

{
  operation: "/",
  left: {
    operation: "+",
    left: 12,
    right: 4
  }
  right: 6
}

این سخت ترین بخش فرآیند است.

ارزیابی

ارزیاب درخت تجزیه تولید شده توسط تجزیه کننده را می گیرد و آن را ارزیابی می کند. ارزیابان معمولا درخت تجزیه را به صورت بازگشتی طی می کنند. با توجه به درخت نحو بالا، ارزیاب ممکن است ابتدا عملوند سمت چپ /عملیات سطح بالا، سپس عملوند سمت راست را ارزیابی کند و سپس نتیجه تقسیم را برگرداند.

ارزیابی عملوند سمت چپ، درخت نحو را به این شکل ساده می کند:

{
  operation: "/",
  left: 16,
  right: 6
} 

که به نوبه خود به نتیجه نهایی ارزیابی می شود:

۲٫۶۶۶۶۶۶۶۶۶۶۶۶۶۶۶۵

AEL: زبان ماشین حساب

قبل از اینکه بتوانیم نوشتن مترجم خود را شروع کنیم، باید زبانی را که ترجمه خواهیم کرد، که من همین الان ساخته‌ام و به آن AEL، مخفف زبان بیان حسابی اشاره می‌کنم، بفهمیم.

این زبان به صورت مجموعه ای از عبارات حسابی متشکل از اعداد و عملگرهای حسابی (جمع +)، -(تفریق و نفی)، *(ضرب)، /(تقسیم)، %(مدول)، ^(توان)، و همچنین پرانتز ()برای گروه بندی نوشته می شود.

مفسر هر عبارت را ارزیابی می کند و نتیجه هر کدام را به ترتیب ارائه شده چاپ می کند. به عنوان مثال با توجه به ورودی زیر …

۳
۲ ^ ۸
(۱۲ % ۷) * (۳ + ۲)
۱۹ / -۹

… مترجم خروجی می دهد:

۳
۲۵۶
۲۵
-۲٫۱۱۱۱۱۱۱۱۱۱۱۱۱۱۱

=AEL همچنین به شما این امکان را می دهد که با استفاده از اپراتور تخصیص متغیر را تعریف کنید . سمت چپ یک شناسه و سمت راست یک عبارت حسابی خواهد بود. یک دستور با یک انتساب مقدار بازگشتی ندارد، بنابراین مفسر خط مربوطه را چاپ نخواهد کرد.

مثلا:

hoursPerDay = 24
minutesPerHour = 60
minutesPerDay = minutesPerHour * hoursPerDay
minutesPerDay
minutesPerDay * 60

خروجی ها:

۱۴۴۰
۸۶۴۰۰

AEL دارای دو متغیر از پیش تعریف شده خواهد بود: piو eکه به ترتیب با مقادیر ۳٫۱۴۱۵۹۲۶۵۳۵۸۹۷۹۳و ۲٫۷۱۸۲۸۱۸۲۸۴۵۹۰۴۵مطابقت دارند.

در نهایت، AEL به شما امکان تعریف توابع را می دهد. یک انتساب تابع نیز از =عملگر استفاده می کند، اما آرگومان سمت چپ باید یک شناسه به دنبال پرانتز باشد، که حاوی صفر یا چند نام آرگومان است که با کاما از هم جدا شده اند. پس از تعریف، یک تابع را می توان با نوشتن یک نام شناسه و به دنبال آن پرانتزهای حاوی صفر یا بیشتر عبارات حسابی که با کاما از هم جدا شده اند فراخوانی کرد.

مثلا:

toDegrees(radians) = radians * 180 / pi
toDegrees(2 * pi)

cylinderVolume(r, h) = pi * r ^ 2 * h
cylinderVolume(2, 4)

خروجی ها:

۳۶۰
۵۰٫۲۶۵۴۸۲۴۵۷۴۳۶۶۹

اکنون که می دانیم زبان چگونه است، می توانیم شروع به نوشتن مترجم کنیم.

مرحله ۱: Lexer

lexer ورودی متن را می گیرد و لیستی از نشانه ها را برمی گرداند. بنابراین، اسکلت lexعملکرد ما باید به شکل زیر باشد:

var lex = function (input) {
  var tokens = [];
  //some magic goes here
  return tokens;
};

ما چندین نوع مختلف توکن داریم. عملگرهایی وجود دارند که با مجموعه کاراکترها تعریف می +-*/^%=(),شوند، اعدادی هستند که از ارقام اعدادی تشکیل شده اند، فضای خالی وجود دارد که lexer ما آن ها را نادیده می گیرد، و شناسه هایی وجود دارد که به عنوان هر رشته ای از کاراکترها که شامل عملگر نیستند، تعریف می شوند. ارقام یا فضای خالی

var isOperator = function (c) { return /[+\-*\/\^%=(),]/.test(c); },
  isDigit = function (c) { return /[0-9]/.test(c); },
  isWhiteSpace = function (c) { return /\s/.test(c); },
  isIdentifier = function (c) 
   { return typeof c === "string" && !isOperator(c) && !isDigit(c) && !isWhiteSpace(c); };

ما یک حلقه ساده برای اسکن متن ورودی ایجاد خواهیم کرد. ما یک متغیر خواهیم داشت cکه با کاراکتر فعلی مطابقت دارد، یک تابع ایجاد می کنیم که advance یک کاراکتر را در ورودی به جلو می برد و کاراکتر بعدی را برمی گرداند، و یک تابع به نام addTokenکه یک نشانه را به لیست نشانه ها اضافه می کند.

var tokens = [], c, i = 0;
var advance = function () { return c = input[++i]; };
var addToken = function (type, value) {
  tokens.push({
    type: type,
    value: value
 });
};
while (i < input.length) {
  c = input[i];
  //...
}

اگر cفضای خالی است، فقط آن را نادیده می گیریم و ادامه می دهیم. اگر cیک اپراتور است، یک نشانه عملگر به لیست اضافه کنید و ادامه دهید. جاوا اسکریپت

if (isWhiteSpace(c)) advance();
else if (isOperator(c)) {
  addToken(c);
  advance();
}

برای سادگی، یک عدد را به عنوان یک سری ارقام تعریف می کنیم که به صورت اختیاری یک نقطه اعشار و یک سری ارقام دیگر را دنبال می کنیم. جاوا اسکریپت

else if (isDigit(c)) {
  var num = c;
  while (isDigit(advance())) num += c;
  if (c === ".") {
    do num += c; while (isDigit(advance()));
  }
  num = parseFloat(num);
  if (!isFinite(num)) throw "Number is too large or too small for a 64-bit double.";
  addToken("number", num);
}

هر شخصیت دیگر یک شناسه است. جاوا اسکریپت

else if (isIdentifier(c)) {
  var idn = c;
  while (isIdentifier(advance())) idn += c;
  addToken("identifier", idn);
}

و فقط در صورتی که چیز عجیبی به سمت ما پرتاب شود: جاوا اسکریپت

else throw "Unrecognized token."; 

پس از اتمام اسکن ورودی، یک نشانه برای مشخص کردن انتهای آن اضافه می کنیم. سپس کارمان تمام شد. جاوا اسکریپت

addToken("(end)");
return tokens;

مرحله ۲: تجزیه کننده

استراتژی های مختلفی برای نوشتن تجزیه کننده وجود دارد. یکی از رایج ترین آنها نوشتن گرامر Backus-Naur و استفاده از نزول بازگشتی است . در این مقاله، با استفاده از تکنیک‌هایی که در مقاله تقدم اپراتور Top Down Douglas Crockford توضیح داده شده است، از یک استراتژی کمتر رایج به نام تجزیه عملگر-اولویت استفاده خواهیم کرد.

تجزیه اولویت عملگر با فرآیند زیر آغاز می شود:

• هر نشانه عملیاتی را با قدرت اتصال سمت چپ و یک تابع عملیاتی مرتبط کنید.
• اگر اپراتور نشانه‌ها را در سمت چپ خود دستکاری می‌کند (مانند +)، آن را با یک تابع نشانه سمت چپ مرتبط کنید (از این پس به اختصار به عنوان led) نامیده می‌شود. اگر اپراتور توکن‌های سمت چپ خود را دستکاری نمی‌کند (مانند unary -)، آن را با یک nullتابع نشانه (از این پس به اختصار به عنوان اختصاراً nud) مرتبط کنید. شناسه ها و اعداد نیز دارای یک nudعملکرد مرتبط با آنها هستند.

پس از انجام این کار، می تواند شروع به تولید درخت تجزیه کند. برای نشان دادن اینکه چگونه این کار می کند، از عبارت حسابی زیر به عنوان مثال استفاده می کنم.

۱۲ + ۴ / ۶

تابع تجزیه کننده با اجرای nudاولین نشانه ( ۱۲) شروع می شود که خود را برمی گرداند. جاوا اسکریپت

{ type: "number", value: 12 }

این تبدیل به سمت چپی می شود که به ledعلامت بعدی ( +) منتقل می کنیم، که به صورت بازگشتی تابع تجزیه کننده را برای تجزیه توکن های باقی مانده فراخوانی می کند. جاوا اسکریپت

{
  type: "+",
  left: { type: "number", value: 12 },
  right: //parse remaining tokens
}

با فراخوانی nudاولین توکن باقیمانده ( ۴) از نو شروع می کنیم که خودش برمی گردد. جاوا اسکریپت

{ type: "number", value: 4 }

این به سمت چپ تبدیل می شود که ما به led علامت بعدی (/) می گذرانیم، که به صورت بازگشتی تابع تجزیه کننده را برای تجزیه توکن های باقی مانده فراخوانی می کند. جاوا اسکریپت

{
  type: "+",
  left: { type: "number", value: 12 },
  right: {
    type: "/"
    left: { type: "number", value: 4 },
    right: //parse remaining tokens
  }
}

nudاولین علامت باقی مانده را ( ) می نامیم ۶که خودش برمی گردد. این پایان لیست نشانه ها است، بنابراین درخت تجزیه کامل است. جاوا اسکریپت

{
  type: "+",
  left: { type: "number", value: 12 },
  right: {
    type: "/"
    left: { type: "number", value: 4 },
    right: { type: "number", value: 6 }
  }
}

اگر اکنون و را تغییر +دهیم /، خواهیم دید که چگونه قدرت الزام آور وارد بازی می شود. /دارای قدرت اتصال بالاتر از +, بنابراین محکم تر به عملوندهای اطراف خود متصل می شود.

۱۲ / ۴ + ۶

ما مانند قبل شروع می کنیم: jscsript

{
  type: "/",
  left: { type: "number", value: 12 },
  right: //parse remaining tokens
}

اما این بار، پس از فراخوانی nudاز ۴، یک نشانه را به جلو نگاه خواهیم کرد و خواهیم دید که +اولویت کمتری نسبت به علامت دارد /. این به این معنی است که ما ۴در سمت راست آن را می چسبانیم و سپس کل درخت فعلی را به led رد +می کنیم، که باعث می شود به این درخت تجزیه برسید: جاوا اسکریپت

{
  type: "+",
  left: {
    type: "/",
    left: { type: "number", value: 12 },
    right: { type: "number", value: 4 }
  },
  right: { type: "number", value: 6 },
}

اکنون که درک درستی از فرآیند تجزیه داریم، می توانیم تجزیه کننده خود را بنویسیم. تجزیه کننده نشانه هایی را که lexer تولید کرده است می پذیرد و یک درخت تجزیه را برمی گرداند، بنابراین اسکلت parse تابع ما به شکل زیر خواهد بود: جاوا اسکریپت

var parse = function (tokens) {
 var parseTree = [];
 //some magic
 return parseTree;
};

ما باید نوعی جدول نماد داشته باشیم که نماد را با یک قدرت اتصال، nud یا led مرتبط کند، و ما به تابعی نیاز داریم که یک نشانه را با نماد مربوطه مرتبط کند. جاوا اسکریپت

var symbols = {},
symbol = function (id, nud, lbp, led) {
  var sym = symbols[id] || {};
  symbols[id] = {
    lbp: sym.lbp || lbp,
    nud: sym.nud || nud,
    led: sym.led || led
  };
};

var interpretToken = function (token) {
  var sym = Object.create(symbols[token.type]);
  sym.type = token.type;
  sym.value = token.value;
  return sym;
};

ما به راهی نیاز داریم تا ببینیم توکن فعلی چیست و راهی برای پیشروی به توکن بعدی. جاوا اسکریپت

var i = 0, token = function () { return interpretToken(tokens[i]); };
var advance = function () { i++; return token(); };

اکنون می‌توانیم یک تابع عبارت بنویسیم که درخت تجزیه یک عبارت را مطابق روشی که در بالا توضیح داده شد تولید می‌کند: جاوا اسکریپت

var expression = function (rbp) {
  var left, t = token();
  advance();
  if (!t.nud) throw "Unexpected token: " + t.type;
  left = t.nud(t);
  while (rbp < token().lbp) {
    t = token();
    advance();
    if (!t.led) throw "Unexpected token: " + t.type;
  left = t.led(left);
 }
 return left;
};

اکنون می توانیم توابع infix و prefix را ایجاد کنیم که می توانیم از آنها برای تعریف عملگرها استفاده کنیم: جاوا اسکریپت

var infix = function (id, lbp, rbp, led) {
  rbp = rbp || lbp;
  symbol(id, null, lbp, led || function (left) {
    return {
      type: id,
      left: left,
      right: expression(rbp)
    };
  });
},
prefix = function (id, rbp) {
  symbol(id, function () {
    return {
      type: id,
      right: expression(rbp)
    };
  });
};

اکنون می‌توانیم همه عملگرهای حسابی را به‌صورت اعلامی تعریف کنیم. توجه داشته باشید که عملگر توان ( ^) دارای قدرت اتصال راست است که از قدرت اتصال سمت چپ آن کوچکتر است. این به این دلیل است که قدرت تداعی کننده درست است . جاوا اسکریپت

prefix("-", 7);
infix("^", 6, 5);
infix("*", 4);
infix("/", 4);
infix("%", 4);
infix("+", 3);
infix("-", 3);

برخی از عملگرها وجود دارند که فقط به عنوان جداسازی یا مرزبندی پایانی وجود دارند. آنها پیشوند یا پسوند نیستند، بنابراین کافی است آنها را به جدول نماد اضافه کنید. جاوا اسکریپت

symbol(",");
symbol(")");
symbol("(end)");

پرانتز nudفقط چیزی را که داخل آن است برمی‌گرداند و عدد nudفقط خودش را برمی‌گرداند. جاوا اسکریپت

symbol("(", function () {
  value = expression(2);
  if (token().type !== ")") throw "Expected closing parenthesis ')'";
  advance();
  return value;
});
symbol("number", function (number) {
    return number;
});

شناسه nud و =اپراتور nudپیچیده تر هستند زیرا رفتاری وابسته به زمینه دارند.

symbol("identifier", function (name) {
  if (token().type === "(") {
    var args = [];
    if (tokens[i + 1].type === ")") advance();
    else {
      do {
        advance();
        args.push(expression(2));
      } while (token().type === ",");
      if (token().type !== ")") throw "Expected closing parenthesis ')'";
    }
    advance();
    return {
      type: "call",
      args: args,
      name: name.value
    };
  }
  return name;
});
infix("=", 1, 2, function (left) {
    if (left.type === "call") {
      for (var i = 0; i < left.args.length; i++) {
        if (left.args[i].type !== "identifier") throw "Invalid argument name";
      }
      return {
        type: "function",
        name: left.name,
        args: left.args,
        value: expression(2)
      };
    } else if (left.type === "identifier") {
      return {
        type: "assign",
        name: left.value,
        value: expression(2)
      };
    }
    else throw "Invalid lvalue";
});

حالا که همه چیزهای سخت از بین رفته‌اند، می‌توانیم فقط چسب تکمیلی را روی آن بگذاریم. جاوا اسکریپت

var parseTree = [];
while (token().type !== "(end)") {
  parseTree.push(expression(0));
}
return parseTree;

مرحله ۳: ارزیاب

ارزیاب درخت تجزیه تولید شده توسط تجزیه کننده را می پذیرد، هر مورد را ارزیابی می کند و خروجی ارزیابی شده را تولید می کند. اسکلت تابع ارزیابی ما به شکل زیر خواهد بود: جاوا اسکریپت

var evaluate = function (parseTree) {
  var parseNode = function (node) {
  //magic goes here
  };
  var output = "";
  for (var i = 0; i < parseTree.length; i++) {
    var value = parseNode(parseTree[i]);
    if (typeof value !== "undefined") output += value + "\n";
  }
  return output;
};

تعریف رفتار عملگرها و همه متغیرها و توابع از پیش تعریف شده ساده است:

var operators = {
    "+": function(a, b) {
        return a + b;
    },
    "-": function(a, b) {
        if (typeof b === "undefined") return -a;
        return a - b;
    },
    "*": function(a, b) {
        return a * b;
    },
    "/": function(a, b) {
        return a / b;
    },
    "%": function(a, b) {
        return a % b;
    },
    "^": function(a, b) {
        return Math.pow(a, b);
    }
};

var variables = {
    pi: Math.PI,
    e: Math.E
};

var functions = {
    sin: Math.sin,
    cos: Math.cos,
    tan: Math.cos,
    asin: Math.asin,
    acos: Math.acos,
    atan: Math.atan,
    abs: Math.abs,
    round: Math.round,
    ceil: Math.ceil,
    floor: Math.floor,
    log: Math.log,
    exp: Math.exp,
    sqrt: Math.sqrt,
    max: Math.max,
    min: Math.min,
    random: Math.random
};
var args = {};

حالا می توانیم گوشت ارزیاب خود را بریزیم و کارمان تمام است. تابع parseNodeبه صورت بازگشتی درخت تجزیه را پیمایش و ارزیابی می کند.

var parseNode = function (node) {
  if (node.type === "number") return node.value;
  else if (operators[node.type]) {
    if (node.left) return operators[node.type](parseNode(node.left), parseNode(node.right));
    return operators[node.type](parseNode(node.right));
  }
  else if (node.type === "identifier") {
    var value = args.hasOwnProperty(node.value) ? args[node.value] : variables[node.value];
    if (typeof value === "undefined") throw node.value + " is undefined";
    return value;
  }
  else if (node.type === "assign") {
    variables[node.name] = parseNode(node.value);
  }
  else if (node.type === "call") {
    for (var i = 0; i < node.args.length; i++) node.args[i] = parseNode(node.args[i]);
    return functions[node.name].apply(null, node.args);
  }
  else if (node.type === "function") {
    functions[node.name] = function () {
      for (var i = 0; i < node.args.length; i++) {
        args[node.args[i].value] = arguments[i];
      }
      var ret = parseNode(node.value);
      args = {};
      return ret;
    };
  }
};

همه اش را بگذار کنار هم

حالا می‌توانیم همه چیز را جمع کنیم و تکه‌های تو را در یک calculate عملکرد واحد کنار هم قرار دهیم. جاوا اسکریپت

var calculate = function (input) {
  try {
    var tokens = lex(input);
    var parseTree = parse(tokens);
    var output = evaluate(parseTree);
    return output;
  } catch (e) {
    return e;
  }
};

کار بعدی چیه

چیزهای زیادی وجود دارد که می توانید به زبان اضافه کنید تا آن را مفیدتر کنید یا فقط ببینید کارها چگونه کار می کنند. برخی از اضافه‌ها نسبتاً آسان خواهند بود، برخی دیگر می‌توانند بسیار سخت باشند.

چیزهای آسان

• با اضافه کردن توابع از پیش تعریف شده خود بازی کنید.
• با اعداد قدرت صحافی کمانچه بزنید تا ببینید که چگونه نحوه ارزیابی عبارات را تغییر می دهد.
• به نمادهای علمی در حروف اعداد اجازه دهید یا استفاده از لفظ اعداد دودویی یا هگزیدسیمال را ممکن کنید.

چیزهای متوسط

• اجازه دستکاری انواع بیشتری از داده ها، مانند رشته ها، بولی ها و آرایه ها را می دهد.
• به توابع اجازه دهید چندین دستور داشته باشند و مقادیر را به صورت مشروط برگردانند.
• ارزیاب را با یک کامپایلر یا ترانسپایلر جایگزین کنید که درخت تجزیه را می گیرد و کد را به زبان دیگری خروجی می دهد.
• یک مدیریت بسته بسازید که به شما امکان می دهد کد را از فایل های دیگر وارد کنید.

چیزهای سخت تر

• بهینه‌سازی‌هایی را اجرا کنید تا محاسبات سریع‌تر انجام شوند.
• تابعیت را شهروندان درجه یک قرار دهید و اجازه تعطیلی بدهید.
• آن را طوری تنظیم کنید که همه داده ها به صورت تنبلی ارزیابی شوند.

اگر می دانید چگونه برخی از این کارها را انجام دهید، آماده هستید که شروع به ساخت مفسر و کامپایلر برای زبان های خاص دامنه خود کنید.