Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Контекстно вільні граматики. Зав’язок контекстно вільної граматики і автомата з магазинною пам’яттю
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
ТГВ
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Лiнгвiстичне забезпечення САПР
Група:
КН-413
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
кафедра САПР
ЗВІТ
до лабораторної роботи №5
на тему:
«Контекстно вільні граматики. Зав’язок контекстно вільної граматики і автомата з магазинною пам’яттю»
з курсу:
«Лінгвістичне забезпечення САПР»
Львів 2010
МЕТА РОБОТИ
Вивчити особливості використання контекстно вільних граматик та їх зв'язок з автоматами з магазинною пам’яттю.
ЛАБОРАТОРНЕ ЗАВДАННЯ
Побудувати дерево виводу, сформувати КВ-граматику і розробити МП-автомат для наступної мови:
21. (a+b)/c*a
ХІД РОБОТИ
1. Побудова дерева виводу.
*
<І >
2. Формування КВ-граматики.
G=(VT, VN, , P).
VT={a, b, c, +, /, * , (, )};
VN={S, V, M, N, І, O};
=S
3. Побудова МП-автомата
Q={S1, S2};
Σ={a, b, c, +, /, *, ¬};
Г={ S, V, M, І, O, a, b, c, +, /, *, (, ), };
δ
q0=S1;
Z0=;
F=ДОПУСТИТИ;
Таблиці станів:
S1
a
b
c
+
/
*
(
)
¬
S
S1,ТР., S→ІOІOV
V
S2, ТР., V→)M(
M
S1, ТР., M→ІOІ
О
S1, ТР., O→+
S2,ТР.,
O→/
S2,ТР.,
O→*
І
S1, ТР., І→a
S2, ТР.,
І→a
S2,ТР.,
І→b
S2,ТР.,
І→c
S2
a
b
c
+
/
*
(
)
¬
a
S1,Зсув Вишт.
b
S2,Зсув Вишт.
c
S1,Зсув Вишт.
+
S1,Зсув Вишт.
/
S1,Зсув Вишт.
*
S1,Зсув Вишт.
(
S1,Зсув Вишт.
)
S1,Зсув Вишт.
ДОП.
ТЕКСТ ПРОГРАМИ
import java.util.*;
import java.io.*;
class Magazine {
public byte size = 20;
public byte startedQuantityOfMagazine = 2;
private char[] mag = new char[size];
private byte i, p;
public byte s;
public int f;//F(0 - не допуск, 1 - допуск)
public String str;
public Magazine(String str) {
this.str = str;
s = 1; f = -1;
mag[0] = '^'; p++;
mag[1] = 'S'; p++;
for (i = 3; i < size - 1; i++)
{
mag[i] = ' ';
}
}
public void push(char c)
{
if (p == size - 1)
{
System.out.println("Magazine is full.");
}
else
{
mag[p] = c; p++;
}
}
public void pop()
{
p--;
mag[p] = ' ';
}
public void printAllMagazine()
{
for (int i=0; i<p; i++){
System.out.print(mag[i]);
}
}
public char HeadOfMagazine()
{
return mag[p - 1];
}
public byte tablesOFStanes()
{
byte x=0;
switch(this.s) {
case 1:
if (HeadOfMagazine() == 'S' && str.charAt(0) == '(')
{
x = 1;
pop();
push('I'); push('O'); push('I'); push('O'); push('V');
}
else if (HeadOfMagazine() == 'V' && str.charAt(0) == '(')
{
x = 1;
pop();
push(')'); push('M'); push('(');
this.s = 2;
}
else if (HeadOfMagazine() == 'M' && str.charAt(0) == 'a')
{
x = 1;
pop();
push('I'); push('O'); push('I');
}
else if (HeadOfMagazine() == 'I' && str.charAt(0) == 'a')
{
x = 1;
pop();
push('a');
this.s = 2;
}
else if (HeadOfMagazine() == 'O' && str.charAt(0) == '+')
{
x = 1;
pop();
push('+');
this.s = 2;
}
else if (HeadOfMagazine() == 'I' && str.charAt(0) == 'b')
{
x = 1;
pop();
push('b');
this.s = 2;
}
else if (HeadOfMagazine() == 'O' && str.charAt(0) == '/')
{
x = 1;
pop();
push('/');
this.s = 2;
}
else if (HeadOfMagazine() == 'I' && str.charAt(0) == 'c')
{
x = 1;
pop();
push('c');
this.s = 2;
}
else if (HeadOfMagazine() == 'O' && str.charAt(0) == '*')
{
x = 1;
pop();
push('*');
this.s = 2;
}
break;
case 2:
if (HeadOfMagazine() == '(' && str.charAt(0) == '(')
{
pop();
this.str = str.substring(1, str.length());
}
else if (HeadOfMagazine() == 'M' && str.charAt(0) == 'a')
{
this.s = 1;
x = 1;
}
else if (HeadOfMagazine() == 'a' && str.charAt(0) == 'a')
{
pop();
this.str = str.substring(1, str.length());
this.s = 1;
}
else if (HeadOfMagazine() == '+' && str.charAt(0) == '+')
{
pop();
this.str = str.substring(1, str.length());
this.s = 1;
}
else if (HeadOfMagazine() == 'b' && str.charAt(0) == 'b')
{
pop();
this.str = str.substring(1, str.length());
}
else if (HeadOfMagazine() == ')' && str.charAt(0) == ')')
{
pop();
this.str = str.substring(1, str.length());
this.s = 1;
}
else if (HeadOfMagazine() == '/' && str.charAt(0) == '/')
{
pop();
this.str = str.substring(1, str.length());
this.s = 1;
}
else if (HeadOfMagazine() == 'c' && str.charAt(0) == 'c')
{
pop();
this.str = str.substring(1, str.length());
this.s = 1;
}
else if (HeadOfMagazine() == '*' && str.charAt(0) == '*')
{
pop();
this.str = str.substring(1, str.length());
this.s = 1;
}
else if (HeadOfMagazine() == '^' && str.charAt(0) == '-')
{
f = 1;
}
break;
}
return x;
}
}
public class lab {
public static void main(String[] args) {
BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
String str = ""; byte x = 0;
System.out.println("Enter input string: ");
try {str=input.readLine();}catch(IOException e){System.out.println("Помилка вводу-виводу");return;}
System.out.println(str);
str = str + "-";
Magazine m = new Magazine(str);
System.out.println("Input string: " + str);
System.out.println("------------------------------------------------");
System.out.println(" Magazine | Stan | Input string");
System.out.println("------------------------------------------------");
m.printAllMagazine();
System.out.print("| " + m.s + " |");
System.out.print(m.str);
System.out.println();
for (int i = 0; i < str.length(); i++)
{
i -= x;
if (m.f == 0) { break; }
else
{
x = m.tablesOFStanes();
System.out.println("-------------------------------------------------------------------");
m.printAllMagazine();
System.out.print("| " + m.s + " | ");
System.out.print(m.str);
System.out.println();
}
}
if (m.f == 1)
{
System.out.println("$$$$ Input string was allowed. $$$");
}
else
{
System.out.println("$$ Input string wasn't allowed. $$");
}
}
}
РЕЗУЛЬТАТИ ВИКОНАННЯ ПРОГРАМИ
Enter input string:
(a+b)/a*c
(a+b)/a*c
Input string: (a+b)/a*c-
------------------------------------------------
Magazine | Stan | Input string
------------------------------------------------
^S| 1 |(a+b)/a*c-
-------------------------------------------------------------------
^IOIOV| 1 | (a+b)/a*c-
-------------------------------------------------------------------
^IOIO)M(| 2 | (a+b)/a*c-
-------------------------------------------------------------------
^IOIO)M| 2 | a+b)/a*c-
-------------------------------------------------------------------
^IOIO)M| 1 | a+b)/a*c-
-------------------------------------------------------------------
^IOIO)IOI| 1 | a+b)/a*c-
-------------------------------------------------------------------
^IOIO)IOa| 2 | a+b)/a*c-
-------------------------------------------------------------------
^IOIO)IO| 1 | +b)/a*c-
-------------------------------------------------------------------
^IOIO)I+| 2 | +b)/a*c-
-------------------------------------------------------------------
^IOIO)I| 1 | b)/a*c-
-------------------------------------------------------------------
^IOIO)b| 2 | b)/a*c-
-------------------------------------------------------------------
^IOIO)| 2 | )/a*c-
-------------------------------------------------------------------
^IOIO| 1 | /a*c-
-------------------------------------------------------------------
^IOI/| 2 | /a*c-
-------------------------------------------------------------------
^IOI| 1 | a*c-
-------------------------------------------------------------------
^IOa| 2 | a*c-
-------------------------------------------------------------------
^IO| 1 | *c-
-------------------------------------------------------------------
^I*| 2 | *c-
-------------------------------------------------------------------
^I| 1 | c-
-------------------------------------------------------------------
^c| 2 | c-
-------------------------------------------------------------------
^| 1 | -
-------------------------------------------------------------------
^| 1 | -
$$ Input string wasn't allowed. $$
ВИСНОВКИ
На цій лабораторній роботі я ознайомився з правилами побудови і застосування автоматів та перетворювачів з магазинною пам’яттю.
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора