Khoa Khoa học máy tính
ĐỒ ÁN AUTOMAT
Viết chương trình phân tích cú pháp, tạo và hiển thị
cây cú pháp của một biểu thức chính quy.

MỤC LỤC:
Phần mở đầu
Phần I.Cơ sở lí thuyết.
Phần II.Chương trình.
Phần III.Phần code chính của chương trình.
Phần IV.Tài liệu tham khảo.
Phần mở đầu
• Mục đích của việc giải quyết bài toán được giao: Hiểu được định nghĩa về
biểu thức chính qui.Phương pháp phân tích biểu thức chính qui.
• Để thực hiện đò án Viết chương trình phân tích cú pháp, tạo và hiển thị cây
cú pháp của một biểu thức chính quy ta cần phải:
 Thực hiện xử lí chuỗi nhập vào.Xác định xem biểu thức có phải biểu
thức chính qui không.
 Định dạng lại biểu thức.
 Đưa biểu thức về dạng hậu tố.
 Biểu diễn biểu thức chính qui dưới dạng cây nhị phân.
Phần I.Cơ sở lí thuyết
I.Định nghĩa biểu thức chính qui:
Định nghĩa: Biểu thức chính quy được định nghĩa một cách đệ quy như sau:
1. ε là biểu thức chính quy. L(ε)={ε}.
∅ là biểu thức chính quy. L(∅)={∅}.
nếu a∈∑, a là biểu thức chính quy. L(a)={a}.
2. Nếu r, s là các biểu thức chính quy thì:
 ((r)) là biểu thức chính quy. L((r))=L(r);
 r+s là biểu thức chính quy. L(r+s)=L(r)∪L(s);
 r.s là biểu thức chính quy. L(r.s)=L(r).L(s);

• r∅ = ∅r = ∅
• (r + s) t = rt + st
• r (s + t) = rs + rt
4.

Tổng hợp:
• (r* + s*)* = (r*s*)* = (r + s)*
• (rs)*r = r(sr)*
• (r*s)* r* = (r + s)*
5.

Thứ tự ưu tiên của phép toán: * (bao đóng), . (phép nối kết), + (phép hợp).
Ví dụ: Biểu thức chính quy cho ngôn ngữ gồm các xâu nhị phân mà không có hai
số 0 hay hai số 1 liên nhau.
(01)
*
+(10)
*
+0(10)
*
+1(01)
*

hoặc là:
(ε+1)(01)
*
(ε+0)
Thứ tự ưu tiên của phép toán: *, . , +
Do đó: 01
*

using System.Diagnostics;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Text.RegularExpressions;
using System.IO;
namespace Automata
{
public partial class frm_ChuongTrinhChinh : Form
{
RE BieuThucChinhQui = new RE();
Bitmap NoiVe;
Graphics g;
VeNut[] HinhCay;
Point[] ViTriNut;
public frm_ChuongTrinhChinh()
{
InitializeComponent();
ptb_MoPhong.Height = gr_Cay.Height;
ptb_MoPhong.Width = gr_Cay.Width;
KhoiTaoViTri();
NoiVe = new Bitmap(ptb_MoPhong.Width, ptb_MoPhong.Height);
g = Graphics.FromImage(NoiVe);
}
private void KhoiTaoViTri()
{
HinhCay = new VeNut[30];
ViTriNut = new Point[30];

string tempstr = "";
tempstr = Sts.ReadToEnd();
Sts.Close();
fs.Close();
txt_RE.Text = tempstr;
}
}
private void btn_Compile_Click(object sender, EventArgs e)
{
if (txt_RE.Text.Length == 0)
{
MessageBox.Show("Bạn phải nhập vào một Biểu Thức Chính Quy.", "Lỗi!",
MessageBoxButtons.OK, MessageBoxIcon.Error);
txt_RE.Select();
return;
}
try
{
CacLoi errCode = BieuThucChinhQui.CompileWithStats(this.txt_RE.Text,
txt_RE,txt_BanDau,txt_SauDinhDang,txt_Hauto);
if (errCode != CacLoi.DinhDangDung)
{
string sErrSubstring =
txt_RE.Text.Substring(BieuThucChinhQui.GetLastErrorPosition(),
BieuThucChinhQui.GetLastErrorLength());
string sFormat = "Phát hiện lỗi khi biên dịch \nMã lỗi : {0}\nTại vị
trí thứ : {1}\nKý tự : {2}";
sFormat = String.Format(sFormat, errCode.ToString(),
BieuThucChinhQui.GetLastErrorPosition(), sErrSubstring);
txt_RE.Select(BieuThucChinhQui.GetLastErrorPosition(),

else
kq = false;
return kq;
}
private void TaoChiSoThuTu(ref CayNhiPhan CayCanVe)
{
if (CayCanVe.ConTrai!=null)
{
CayCanVe.GanThuTuChoConTrai();
TaoChiSoThuTu(ref CayCanVe.ConTrai);
}
if (CayCanVe.ConPhai!=null)
{
CayCanVe.GanThuTuChoConPhai();
TaoChiSoThuTu(ref CayCanVe.ConPhai);
}
}
private void TaoThuCacNutCay(CayNhiPhan CayCanVe)
{
TaoChiSoThuTu(ref CayCanVe);
GiaTri[0] = CayCanVe.GiaTri;
DuyetHetMang(CayCanVe);
}
string[] GiaTri = new string[30];
CayNhiPhan Phu;
private void ChoVaoMangVe(CayNhiPhan CayCanVe)
{
for (int i = 0; i < GiaTri.Length; i++)
{
if (i == CayCanVe.ThuTu)

{
if (GiaTri[i] != "")
{
if (GiaTri[i] == "." || GiaTri[i] == "*" || GiaTri[i] == "+")
{
HinhCay[i] = new VeNut(ViTriNut[i].X, ViTriNut[i].Y, GiaTri[i],
"ToanTu");
HinhCay[i].HienThi(g);
if (i != 0)
{
HinhCay[i].NoiNut(HinhCay[(i - 1) / 2], HinhCay[i], g);
}
else
{
}
ptb_MoPhong.Image = NoiVe;
}
else
{
HinhCay[i] = new VeNut(ViTriNut[i].X, ViTriNut[i].Y, GiaTri[i],
"ToanHang");
HinhCay[i].HienThi(g);
if (i != 0)
{
HinhCay[i].NoiNut(HinhCay[(i - 1) / 2], HinhCay[i], g);
}
else
{
}
ptb_MoPhong.Image = NoiVe;