API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jun 19th, 2019
89
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.19 KB | None | 0 0
raw download clone embed print report
  1. package main
  2.  
  3. import (
  4. "fmt"
  5. "io/ioutil"
  6. "os"
  7. )
  8.  
  9. var (
  10. graph = make(map[string]*Vertex)
  11. formal_args = make(map[string]int)
  12. curFunc string
  13. count = 1
  14. time = 1
  15. )
  16.  
  17. type Lexeme struct {
  18. //Лексема
  19. id int // 0 - это спецсимвол , 1 - константа , 2 - идентификатор
  20. lex string // сама лексема
  21. }
  22.  
  23. type Vertex struct {
  24. comp , t1 , low , args, visited int
  25. n string //имя функции , название вершины
  26. edges map[string]*Vertex //список инцидентности
  27. }
  28.  
  29. type Stack []*Vertex // Структура - стек указателей на вершины, нужная для алг Тарьяна
  30.  
  31. func pop(s Stack) (Stack, *Vertex) { //Поп() из стека
  32. l := len(s)
  33. return s[:l-1], s[l-1]
  34. }
  35.  
  36. func push(s Stack , v *Vertex) Stack { return append(s, v) } // Пуш() в стек
  37.  
  38. func parse_program(lexemes *[]Lexeme , i int) int{
  39. /**
  40. Главная функция парсинга
  41. */
  42. if i < len(*lexemes){
  43. i = parse_program(lexemes , parse_function(lexemes , i))
  44. }
  45. return i
  46. }
  47.  
  48. func parse_function(lexemes *[]Lexeme , i int) int {
  49. /**
  50. Парсинг функции
  51. */
  52. if (*lexemes)[i].id == 2{
  53. curFunc = (*lexemes)[i].lex //текущая функция , глобальная переменная;
  54. if graph[curFunc] == nil { //Если такой функции еще не было
  55. graph[curFunc] = &Vertex{n : curFunc , edges: make(map[string]*Vertex), args: -1, visited: 1}
  56. }
  57. i++ //увеличиваем позицию в лексемах
  58. if(*lexemes)[i].lex == "(" {
  59. j := 0
  60. formal_args = make(map[string]int)
  61. i++
  62. if(*lexemes)[i].lex != ")" {
  63. i , j = parse_idlist(lexemes , i , j)
  64. if (graph[curFunc].args != -1) && (graph[curFunc].args != j) {
  65. /*error()*/ fmt.Print("1") ; os.Exit(0)
  66. } else {
  67. graph[curFunc].args = j
  68. }
  69. }
  70. }
  71. i++
  72. if(*lexemes)[i].lex == ":="{
  73. i++
  74. i = parse_expr(lexemes , i)
  75. if(*lexemes)[i].lex == ";" {
  76. i++
  77. return i
  78. } else{
  79. error()
  80. }
  81. } else{
  82. error()
  83. }
  84. } else {
  85. error()
  86. }
  87. return i
  88. }
  89.  
  90. func parse_idlist(lexemes *[]Lexeme, i int, j int) (int, int) {
  91. /**
  92. Парсер аргументов функций
  93. */
  94. formal_args[(*lexemes)[i].lex] = 1
  95. i++ ; j++
  96. if i < len(*lexemes) {
  97. if (*lexemes)[i].lex == "," {
  98. i++ //Если запятая , то рекурсивно запускаем заново
  99. i, j = parse_idlist(lexemes, i, j)
  100. return i, j
  101. }
  102. if (*lexemes)[i].lex == ")" {
  103. return i, j
  104. }
  105. } else {
  106. error()
  107. }
  108. return 0, 0
  109. }
  110.  
  111. func parse_factor(lexemes *[]Lexeme, i int) int {
  112. if i < len(*lexemes) {
  113. if (*lexemes)[i].id == 1 {
  114. i++
  115. return i
  116. }
  117. if (*lexemes)[i].id == 2 {
  118. i++
  119. if i < len(*lexemes) && (*lexemes)[i].lex == "(" {
  120. var j, k int
  121. k = i - 1
  122. if graph[(*lexemes)[k].lex] == nil {
  123. graph[(*lexemes)[k].lex] = &Vertex{n: (*lexemes)[k].lex, edges: make(map[string]*Vertex), args: -1}
  124. }
  125. i++
  126. i, j = parse_aal(lexemes, i , 0)
  127. if graph[(*lexemes)[k].lex].args != -1 {
  128. if graph[(*lexemes)[k].lex].args != j {
  129. error()
  130. }
  131. } else {
  132. graph[(*lexemes)[k].lex].args = j
  133. }
  134. graph[curFunc].edges[(*lexemes)[k].lex] = graph[(*lexemes)[k].lex]
  135. return i
  136. } else if formal_args[(*lexemes)[i-1].lex] == 1 {
  137. return i
  138. } else {
  139. error()
  140. }
  141. }
  142. if (*lexemes)[i].lex == "(" {
  143. i++
  144. i = parse_expr(lexemes, i)
  145. if (*lexemes)[i].lex == ")" {
  146. i++
  147. return i
  148. } else {
  149. error()
  150. }
  151. }
  152. if (*lexemes)[i].lex == "-" {
  153. i++
  154. i = parse_factor(lexemes, i)
  155. return i
  156. }
  157. }else{
  158. error()
  159. }
  160. return 0
  161. }
  162.  
  163. func parse_expr(lexemes *[]Lexeme , i int) int{
  164. i = parse_compexpr(lexemes, i)
  165. if i < len(*lexemes) {
  166. if (*lexemes)[i].lex == "?" {
  167. i++
  168. i = parse_compexpr(lexemes, i)
  169. if (*lexemes)[i].lex == ":" {
  170. i++
  171. i = parse_expr(lexemes, i)
  172. return i
  173. } else {
  174. error()
  175. }
  176. } else {
  177. return i
  178. }
  179. } else {
  180. error()
  181. }
  182. return 0
  183. }
  184.  
  185. func parse_exprlist(lexemes *[]Lexeme, i int, j int) (int, int) {
  186. i = parse_expr(lexemes, i)
  187. j += 1
  188. if i < len(*lexemes) {
  189. if (*lexemes)[i].lex == "," {
  190. i++
  191. i, j = parse_exprlist(lexemes, i, j)
  192. return i, j
  193. }
  194. if (*lexemes)[i].lex == ")" {
  195. i++
  196. return i, j
  197. }
  198. }else {
  199. error()
  200. }
  201. return 0, 0
  202. }
  203.  
  204. func parse_compexpr(lexemes *[]Lexeme , i int) int{
  205. i = parse_arithexpr(lexemes, i)
  206. if i < len(*lexemes) {
  207. temp := false
  208. mas := [6]string{"=", "<>", "<", ">", "<=", ">="}
  209. for _ , q := range mas{
  210. if (*lexemes)[i].lex == q {
  211. temp = true
  212. }
  213. } ////1234
  214. if temp {
  215. i++
  216. i = parse_arithexpr(lexemes, i)
  217. return i
  218. }
  219. return i
  220. } else {
  221. error()
  222. }
  223. return 0
  224. }
  225.  
  226. func parse_aal(lexemes *[]Lexeme , i int , j int) (int , int){
  227. if i < len(*lexemes) {
  228. if (*lexemes)[i].lex != ")" {
  229. i, j = parse_exprlist(lexemes, i, j)
  230. return i, j
  231. } else {
  232. i++
  233. return i, j
  234. }
  235. }else {
  236. error()
  237. }
  238. return 0, 0
  239. }
  240.  
  241. func parse_arithexpr(lexemes *[]Lexeme, i int) int {
  242. return parse_arithexprx(lexemes,parse_term(lexemes, i))
  243. }
  244.  
  245. func parse_term(lexemes *[]Lexeme, i int) int {
  246. return parse_termx(lexemes, parse_factor(lexemes, i))
  247. }
  248.  
  249. func parse_termx(lexems *[]Lexeme, i int) int {
  250. if i < len(*lexems) {
  251. str := (*lexems)[i].lex
  252. if str == "*" || str == "/" {
  253. i++
  254. i = parse_termx(lexems, parse_factor(lexems, i)) ////1234
  255. }
  256. return i
  257. } else {
  258. error()
  259. }
  260. return 0
  261. }
  262.  
  263. func parse_arithexprx(lexemes *[]Lexeme, i int) int {
  264. if i < len(*lexemes) {
  265. str := (*lexemes)[i].lex
  266. if str == "+" || str == "-" {
  267. i++
  268. i = parse_arithexprx(lexemes, parse_term(lexemes, i))
  269. }
  270. return i
  271. }else {
  272. error()
  273. }
  274. return 0
  275. }
  276.  
  277. func visitTarjan(v *Vertex, s Stack) Stack {
  278. /*
  279. Алгоритм Тарьяна для вычсиления компонент сильной связности
  280. */
  281. v.t1 = time
  282. v.low = time
  283. time++
  284. s = push(s , v)
  285. for _, u := range v.edges {
  286. if u.t1 == 0 {
  287. s = visitTarjan(u, s)
  288. }
  289. if u.comp == 0 && v.low > u.low {
  290. v.low = u.low
  291. }
  292. }
  293. if v.t1 == v.low {
  294. for {
  295. var u *Vertex
  296. s, u = pop(s)
  297. u.comp = count
  298. if u == v {
  299. break
  300. }
  301. }
  302. count++
  303. }
  304. return s
  305. }
  306.  
  307. func tarjan() {
  308. for _, v := range graph {
  309. v.t1 = 0
  310. v.comp = 0
  311. }
  312. s := make(Stack, 0) //Тарьян запуск
  313. for _, v := range graph {
  314. if v.t1 == 0 {
  315. visitTarjan(v, s)
  316. }
  317. }
  318. }
  319.  
  320. func error(){
  321. fmt.Printf("%s" , "error")
  322. os.Exit(0)
  323. }
  324.  
  325. func main() {
  326. var s, _= ioutil.ReadAll(os.Stdin)
  327. runes := []rune(string(s)) //Весь код программы в "рунах"
  328. lexemes := make([]Lexeme, 0) //Срез лексем
  329.  
  330. //Лексер
  331.  
  332. for i := 0; i < len(runes); i++ {
  333. var str = string(runes[i]) //строка по коду ASCII >> конкатенировать в случае := , <= , >=
  334.  
  335. if (runes[i] > 39 && runes[i] < 48) || (runes[i] > 57 && runes[i] < 64) {
  336. /**
  337. Разбор "специальных символов" в программе
  338. */
  339. l := Lexeme{id: 0, lex: str} // новая лексема равная str
  340. if str == ":" || str == "<" || str == ">" {
  341. i++
  342. if runes[i] == 61 || (str == "<" && runes[i] == 62) {
  343. str += string(runes[i]) // конкатенация строки : составные символы
  344. l.lex = str // меняем лексему на новую
  345. } else {
  346. i--
  347. }
  348. }
  349. lexemes = append(lexemes, l) //добавляем лексему в срез лексем
  350. } else if runes[i] >= 48 && runes[i] <= 57{
  351. /**
  352. Разбор "констант" в программе
  353. */
  354. l := Lexeme{id: 1, lex: str} // новая лексема равная str
  355. i++
  356. //chn := false
  357. for runes[i] >= 48 && runes[i] <= 57 { //пока дальше идет число >> конкатенация
  358. str += string(runes[i])
  359. i++
  360. //chn = true
  361. }
  362. i--
  363. l.lex = str
  364. lexemes = append(lexemes , l)
  365. } else if (runes[i] > 64 && runes[i] < 91) || (runes[i] > 96 && runes[i] < 123) {
  366. /**
  367. Разбор "идентификаторов" в программе
  368. */
  369. l := Lexeme{id : 2 , lex : str} // новая лексема равная str
  370. i++
  371. //chn := false
  372. for (runes[i] > 64 && runes[i] < 91) || (runes[i] > 96 && runes[i] < 123) || (runes[i] >= 48 && runes[i] <= 57) {
  373. //пока дальше идет буква или число >> конкатенация
  374. str += string(runes[i])
  375. i++
  376. //chn = true
  377. }
  378. i--
  379. l.lex = str
  380. lexemes = append(lexemes , l)
  381. } else if runes[i] == 10 || runes[i] == 32 {
  382. // если пробел или новая строка , то продолжать
  383. continue
  384. } else {
  385. // если нет ожидаемого символа , выдавать ошибку
  386. error()
  387. }
  388. }
  389. parse_program(&lexemes , 0)
  390. tarjan()
  391. count -= 1
  392. if(count == 0 || lexemes[0].lex == "eval"){
  393. error()
  394. }
  395. fmt.Printf("%d\n", count)
  396. os.Exit(0)
  397. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!